14500 테트로도미노

문제

해당 문제는 4가지 도형의 폴리오미노 모양중에서 배열 안의 최댓값을 찾는 문제입니다.

코드

import sys

tetris = [
    [(0, 0), (1, 0), (2, 0), (3, 0)],
    [(0, 0), (0, 1), (0, 2), (0, 3)],
    [(0, 0), (0, 1), (1, 0), (1, 1)],
    [(0, 0), (1, 0), (2, 0), (2, 1)],
    [(0, 0), (1, 0), (2, 0), (2, -1)],
    [(0, 0), (0, 1), (0, 2), (1, 2)],
    [(0, 0), (0, 1), (0, 2), (-1, 2)],
    [(0, 0), (0, 1), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (1, 0), (2, 0)],
    [(0, 0), (1, 0), (1, 1), (1, 2)],
    [(0, 0), (1, 0), (0, 1), (0, 2)],
    [(0, 0), (1, 0), (1, -1), (2, -1)],
    [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (1, 1), (1, 2)],
    [(0, 0), (0, 1), (-1, 1), (-1, 2)],
    [(0, 0), (0, 1), (0, 2), (1, 1)],
    [(0, 0), (0, 1), (0, 2), (-1, 1)],
    [(0, 0), (1, 0), (2, 0), (1, 1)],
    [(0, 0), (1, 0), (2, 0), (1, -1)],
]
stdin = sys.stdin.read().splitlines()
n, m = map(int, stdin[0].split())
_map = [list(map(int, line.split())) for line in stdin[1:]]
ans = 0

for i in range(n):
    for j in range(m):
        for t in tetris:
            sum = 0
            for a, b in t:
                x = i + a
                y = j + b
                if x < 0 or x >= n or y < 0 or y >= m:
                    continue
                sum += _map[x][y]
            ans = max(sum, ans)
print(ans)

풀이

폴리노이드 모양이 총 19개가 나오는데, 브루트 포스를 사용하여 for 문을 돌면서 최대합을 찾는 방식으로 구현했다.

후기

처음에는 bfs + greed 방식을 사용하여 최대값만 따라가는 식으로 만들었지만,
[1004, 0 , 0, 1004] 같은 배열이 나올 때, 최댓값을 찾지못하고, 십자가 모양은 잡지못해 브루트 포스로 풀었다.

풀고나서 실행시간이 6428ms 였는데 다른 사람의 풀이는 비슷한 방식인데 164ms가 나와 찾아봤다.
https://www.acmicpc.net/source/51413752

40배 차이가 났는데, 방식은 비슷했다. 그 분은 배열을 더 크게 만들어서 x,y검사하는 부분이 없었고, 원소를 딱 한번씩만 접근한 차이가 있었다.

필요한 원소만 접근 + 한번 계산 vs 똑같은 원소에 여러번 접근 + 덧셈 2번, if문 검사 4개로 그만큼 차이가 났다.