문제

링크

풀이

1. 첫 번째 테트로미노 회전, 대칭하여 최댓값 모두 탐색

2. 두 번째 테트로미노 회전, 대칭하여 최댓값 모두 탐색

...

3. 다섯 번째 테트리미노 ~

4. 이 중 합의 최댓값을 출력

회전, 대칭이동한 모든 테트로미노를 리스트로 생성하였다. (0,0)에서부터 (N-1,M-1)까지 모든 테트로미노의 최댓값을 완전탐색을 했다. (0,0)에서 모든 테트로미노 최댓값 계산 --> (0,1)에서 모든 테트로미노 최댓값 계산 --> (0,2) ~ ... --> (N-1,M-1)에서 모든 테트로미노 최댓값 계산 후 가장 최댓값을 출력하도록 구현하였다.

DFS의 풀이로도 해당 문제를 풀 수 있다고 한다. (나중에 DFS로 풀어봐야겠다...)

코드

Python3에서는 시간초과 // Pypy3에서는 통과한다!

이 문제는 삼성 코테 문제로, 삼성 코딩테스트에서는 Python3 서버에서 Pypy3를 지원한다고 합니다.

효과적인 자료구조를 사용하면 Python3에서도 통과한다고 한다. 자료구조를 바꾸기도 해보고, 풀이도 바꿔봤으나 Python3에서 시간초과가 떴다. ㅠㅠ

import sys

N, M = map(int, sys.stdin.readline().split())

board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
result = 0

tetromino = [
    # 1자
    [(0, 0), (0, 1), (0, 2), (0, 3)],
    [(0, 0), (1, 0), (2, 0), (3, 0)],

    # ㅁ자
    [(0, 0), (0, 1), (1, 0), (1, 1)],

    # ㄴ자
    [(0, 0), (1, 0), (2, 0), (2, 1)],
    [(0, 0), (0, 1), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (0, 2), (-1, 2)],
    [(0, 0), (0, 1), (0, 2), (1, 0)],
    [(0, 0), (0, 1), (-1, 1), (-2, 1)],
    [(0, 0), (1, 0), (2, 0), (0, 1)],
    [(0, 0), (1, 0), (1, 1), (1, 2)],
    [(0, 0), (0, 1), (0, 2), (1, 2)],

    # ㄹ자
    [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (-1, 1), (-1, 2)],
    [(0, 0), (1, 0), (1, -1), (2, -1)],
    [(0, 0), (0, 1), (1, 1), (1, 2)],

    # ㅗ자
    [(0, 0), (0, 1), (0, 2), (1, 1)],
    [(0, 0), (1, 0), (2, 0), (1, 1)],
    [(0, 0), (0, 1), (0, 2), (-1, 1)],
    [(0, 0), (1, 0), (2, 0), (1, -1)]
]

for r in range(N):
    for c in range(M):
        for tetro in tetromino:
            mid_sum = 0
            for i in range(len(tetro)):
                nr = r + tetro[i][0]
                nc = c + tetro[i][1]
            # for dx, dy in tetro:
            #     nr = r + dx
            #     nc = c + dy
                if nr < 0 or nr >= N or nc < 0 or nc >= M:
                    break
                mid_sum += board[nr][nc]

            result = max(result, mid_sum)

print(result)