[파이썬] 백준 14500 : 테트로미노 (골드4)

[파이썬] 백준 14500 : 테트로미노 (골드4)

 

14500번: 테트로미노

 

---

문제

---

풀이

0. 방향성 생각

누적합, 기본도형을 이용해서 풀이

기본 도형은 1자 바를 제외하면 2*3 / 3*2 도형에서 2개씩 빼서 만들 수 있다. 모두 10가지

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]
arr_tr = list(zip(*arr))

블록의 회전 대칭을 위해 arr의 전치행렬도 구했다.

 

2. 1자 모양 구하기

def bar_score(array):
    case = []
    for row in array:
        temp = []
        for val in row:
            if not temp : temp = [val]
            else: temp.append(temp[-1]+val)
        max_score = temp[3]
        for i in range(4,len(temp)):
            if temp[i] - temp[i-4] > max_score:
                max_score = temp[i] - temp[i-4]
        case.append(max_score)
    return max(case)

누적합 이용해서 입력 array를 받아서 각  row에서 최대값 구하고 갱신.

 

3. 기본도형 6가지

def block_case(array):
    array_sum = sum(array[0]+array[1])
    case = []
    case.append(array_sum-sum(array[0][0:2])) # ㄴ
    case.append(array_sum-sum(array[0][1:3])) # 리버스 ㄴ
    case.append(array_sum-sum(array[1][0:2])) # ㄱ
    case.append(array_sum-sum(array[1][1:3])) # 리버스 ㄱ
    case.append(array_sum-array[0][0]-array[1][0]) # ㅁ1
    case.append(array_sum-array[0][-1]-array[1][-1]) # ㅁ2
    case.append(array_sum-array[0][0]-array[0][-1]) # ㅗ
    case.append(array_sum-array[1][0]-array[1][-1]) # ㅜ
    case.append(array_sum-array[0][0]-array[1][-1]) # ㄹ1
    case.append(array_sum-array[1][0]-array[0][-1]) # ㄹ2
    return case

3*2 입력을 받아서 두 개씩 빼서 점수를 구한다.

6C2해서 총 15인데 안되는 경우가 5가지 있어서 총 10가지이다.

 

4. 정답 출력

def find_answer(array):
    global answer
    scores = []
    for i in range(len(array)-1):
        for j in range(len(array[0])-2):
            temp = [array[i][j:j+3],array[i+1][j:j+3]]
            scores.extend(block_case(temp))
    return max(scores)

print(max([bar_score(arr),bar_score(arr_tr),find_answer(arr),find_answer(arr_tr)]))

3*2 입력 temp를 만들고 함수에 넣어서 계산한 점수를 얻는다.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]
arr_tr = list(zip(*arr))

def bar_score(array):
    case = []
    for row in array:
        temp = []
        for val in row:
            if not temp : temp = [val]
            else: temp.append(temp[-1]+val)
        max_score = temp[3]
        for i in range(4,len(temp)):
            if temp[i] - temp[i-4] > max_score:
                max_score = temp[i] - temp[i-4]
        case.append(max_score)
    return max(case)


def block_case(array):
    array_sum = sum(array[0]+array[1])
    case = []
    case.append(array_sum-sum(array[0][0:2]))
    case.append(array_sum-sum(array[0][1:3]))
    case.append(array_sum-sum(array[1][0:2]))
    case.append(array_sum-sum(array[1][1:3]))
    case.append(array_sum-array[0][0]-array[1][0])
    case.append(array_sum-array[0][-1]-array[1][-1])
    case.append(array_sum-array[0][0]-array[0][-1])
    case.append(array_sum-array[1][0]-array[1][-1])
    case.append(array_sum-array[0][0]-array[1][-1])
    case.append(array_sum-array[1][0]-array[0][-1])
    return case

def find_answer(array):
    global answer
    scores = []
    for i in range(len(array)-1):
        for j in range(len(array[0])-2):
            temp = [array[i][j:j+3],array[i+1][j:j+3]]
            scores.extend(block_case(temp))
    return max(scores)

print(max([bar_score(arr),bar_score(arr_tr),find_answer(arr),find_answer(arr_tr)]))

 

코멘트

노가다 문제