BOJ14500 테트로미노

문제

BOJ14500 테트로미노
골드V | 백준 14500 | Python3 파이썬 풀이

삼성 SW 역량 테스트 기출 문제이다.

알고리즘

브루트포스 문제이다. 그냥 전부 다 구현해서 전부 다 실행해보고 가능한 경우를 세어보면 된다. 문제가 매우 어려워보이지만 조건이 생각보다 간단하므로 전혀 어렵지 않은 문제이다. (만약 테트로미노를 여러 개 놓을 수 있을 때 최댓값이었다면 DP가 섞여 플래티넘 수준의 문제가 되었을 것 같다)

테트로미노를 덮는 것을 어떻게 구현하느냐가 관건인 문제인데, 어차피 2차원 배열 상에서 덮는 곳은 배열의 인덱스로 계산되므로, 각 테트로미노의 상대 인덱스값으로 나열해 저장해주면 된다.

하지만 이 문제는 종이 위에 단 하나의 테트로미노만 놓아 그 테트리미노가 덮는 네 칸의 합 중 최댓값을 구해주는 것이다.

모든 칸에 대해 그 칸을 시작으로 놓을 수 테트로미노의 경우의 수를 전부 계산하고, 그 중 네 칸의 합이 최대가 되는 값을 구하면 된다.

tetromino 리스트에 각 테트로미노의 상대적 (특정 칸 기준) 인덱스를 전부 넣어주었다.

이중 for문을 돌며 각 자리에 가능한 테트로미노를 놓고 그 테트로미노가 덮는 칸들의 합 중 최댓값을 저장한다.

그리고 DFS 풀이가 있었다. DFS를 이용해서는 풀어보지 않았는데, 난이도 기여 내용을 살펴보다 알게 되었는데 DFS로 푸는 풀이가 정말 신기하다. 이 블로그(내용이 재밌다)에 자세하기 나와있다.

코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
papers = [list(map(int, input().split())) for _ in range(N)]

tetromino = []

# O O O O
tetromino.append([(0, 0), (0, 1), (0, 2), (0, 3)])

# O
# O
# O
# O
tetromino.append([(0, 0), (1, 0), (2, 0), (3, 0)])

# O O
# O O
tetromino.append([(0, 0), (0, 1), (1, 0), (1, 1)])

# O O O
# O
tetromino.append([(0, 0), (0, 1), (0, 2), (1, 0)])

# O O O
#     O
tetromino.append([(0, 0), (0, 1), (0, 2), (1, 2)])

# O
# O O O
tetromino.append([(0, 0), (1, 0), (1, 1), (1, 2)])

#     O
# O O O
tetromino.append([(0, 2), (1, 0), (1, 1), (1, 2)])

# O O
# O
# O
tetromino.append([(0, 0), (0, 1), (1, 0), (2, 0)])

# O O
#   O
#   O
tetromino.append([(0, 0), (0, 1), (1, 1), (2, 1)])

# O
# O
# O O
tetromino.append([(0, 0), (1, 0), (2, 0), (2, 1)])

#   O
#   O
# O O
tetromino.append([(0, 1), (1, 1), (2, 0), (2, 1)])

# O O O
#   O
tetromino.append([(0, 0), (0, 1), (0, 2), (1, 1)])

#   O
# O O O
tetromino.append([(0, 1), (1, 0), (1, 1), (1, 2)])

# O
# O O
# O
tetromino.append([(0, 0), (1, 0), (1, 1), (2, 0)])

#   O
# O O
#   O
tetromino.append([(0, 1), (1, 0), (1, 1), (2, 1)])

#   O
# O O
# O
tetromino.append([(0, 1), (1, 0), (1, 1), (2, 0)])

# O
# O O
#   O
tetromino.append([(0, 0), (1, 0), (1, 1), (2, 1)])

#   O O
# O O
tetromino.append([(0, 1), (0, 2), (1, 0), (1, 1)])

# O O
#   O O
tetromino.append([(0, 0), (0, 1), (1, 1), (1, 2)])

ans = 0
# 종이 위 모든 칸에 대해 그 칸에서 시작하는 모든 경우의 수
for i in range(N):
    for j in range(M):
    	# 모든 테트로미노
        for tet in tetromino:
            # 테트로미노가 덮는 범위가 종이 밖으로 나가면 except
            try:
                a1 = papers[i + tet[0][0]][j + tet[0][1]]
                a2 = papers[i + tet[1][0]][j + tet[1][1]]
                a3 = papers[i + tet[2][0]][j + tet[2][1]]
                a4 = papers[i + tet[3][0]][j + tet[3][1]]
                s = a1 + a2 + a3 + a4
            except:
                s = 0
            
            # 최댓값 저장
            ans = max(ans, s)

print(ans)

결과

브루트포스 문제 답게 느린 파이썬도 넉넉하게 통과할 수 있다.

solved.ac 난이도 기여