[백준 14500] 테트로미노

1. 문제

www.acmicpc.net/problem/14500

17136번: 색종이 붙이기

2. 접근 방법

매우 직관적으로 풀었습니다.

 

일단 N, M이 500을 넘지 않기 때문에 완탐을 해도 될 것이라는 생각을 했기 때문이죠 ^-^

 

총 19가지의 경우의 수가 있지만 O(19NM)은 결국 O(NM)이기 때문임다.

3. 코드

python

def isRoad(x, y):
    global N, M
    if x < 0 or x >= M or y < 0 or y >= N:
        return False
    return True

def findSum(x, y):
    global board, ans
    max_total = 0
    # 1-1 (오른쪽으로 4개)
    if isRoad(x+3, y):
        temp_total = sum(board[y][x:x+4])
        max_total = max(temp_total, max_total)
    # 1-2 (아래쪽으로 4개)
    if isRoad(x, y+3):
        temp_total = board[y][x] + board[y+1][x] + board[y+2][x] + board[y+3][x]
        max_total = max(temp_total, max_total)

    # 2-1 (오른쪽 한개, 아래쪽 한개, 오른쪽 아래 1개)
    if isRoad(x+1, y+1):
        temp_total = sum(board[y][x:x+2]) + sum(board[y+1][x:x+2])
        max_total = max(temp_total, max_total)

    # 3-1 (ㄴ모양)
    if isRoad(x+1, y+2):
        temp_total = board[y][x] + board[y+1][x] + board[y+2][x] + board[y+2][x+1]
        max_total = max(temp_total, max_total)

    # 3-2 (ㅢ 모양)
    if isRoad(x+2, y-1):
        temp_total = sum(board[y][x:x+3]) + board[y-1][x+2]
        max_total = max(temp_total, max_total)

    # 3-3 (ㄱ 모양)
    if isRoad(x + 1, y + 2):
        temp_total = sum(board[y][x:x + 2]) + board[y + 1][x + 1] + board[y + 2][x + 1]
        max_total = max(temp_total, max_total)

    # 3-4 (ㅣㅡ 모양)
    if isRoad(x+2, y) and isRoad(x, y+1):
        temp_total = sum(board[y][x:x+3]) + board[y+1][x]
        max_total = max(temp_total, max_total)

    # 3-1 대칭
    if isRoad(x+1, y-2):
        temp_total = sum(board[y][x:x+2]) + board[y-1][x+1] + board[y-2][x+1]
        max_total = max(temp_total, max_total)
    # 3-2 대칭
    if isRoad(x+2, y+1):
        temp_total = board[y][x] + sum(board[y+1][x:x+3])
        max_total = max(temp_total, max_total)
    # 3-3 대칭
    if isRoad(x+1, y) and isRoad(x, y+2):
        temp_total = sum(board[y][x:x+2]) + board[y+1][x] + board[y+2][x]
        max_total = max(temp_total, max_total)
    # 3-4 대칭
    if isRoad(x+2, y+1):
        temp_total = sum(board[y][x:x+3]) + board[y+1][x+2]
        max_total = max(temp_total, max_total)

    # 4-1 (|-|모양)
    if isRoad(x+1, y+2):
        temp_total = board[y][x] + board[y+1][x] + board[y+1][x+1] + board[y+2][x+1]
        max_total = max(temp_total, max_total)

    # 4-2 (_|-모양)
    if isRoad(x+2, y-1):
        temp_total = sum(board[y][x:x+2]) + board[y-1][x+1] + board[y-1][x+2]
        max_total = max(temp_total, max_total)
    # 4-1 대칭
    if isRoad(x+1, y-2):
        temp_total = board[y][x] + sum(board[y-1][x:x+2]) + board[y-2][x+1]
        max_total = max(temp_total, max_total)
    # 4-2 대칭
    if isRoad(x+2, y+1):
        temp_total = sum(board[y][x:x+2]) + board[y+1][x+1] + board[y+1][x+2]
        max_total = max(temp_total, max_total)

    # 5-1 (ㅜ 모양)
    if isRoad(x+2, y) and isRoad(x+1, y+1):
        temp_total = sum(board[y][x:x+3]) + board[y+1][x+1]
        max_total = max(temp_total, max_total)

    # 5-2 (ㅏ모양)
    if isRoad(x+1, y+1) and isRoad(x, y+2):
        temp_total = board[y][x] + sum(board[y+1][x:x+2]) + board[y+2][x]
        max_total = max(temp_total, max_total)

    # 5-3 (ㅗ모양)
    if isRoad(x+2, y) and isRoad(x+1, y-1):
        temp_total = sum(board[y][x:x+3]) + board[y-1][x+1]
        max_total = max(temp_total, max_total)

    # 5-4 (ㅓ모양)
    if isRoad(x+1, y-1) and isRoad(x+1, y+1):
        temp_total = sum(board[y][x:x+2]) + board[y-1][x+1] + board[y+1][x+1]
        max_total = max(temp_total, max_total)

    if max_total > ans:
        ans = max_total

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

for y in range(N):
    for x in range(M):
        findSum(x, y)

print(ans)

4. 마치며

첫 코드가 직관적이고 디버깅하기에는 가장 용이하지만,

코드를 조금 줄여보고자 수정을 해보았습니다.

 

def isRoad(x, y):
    global N, M
    if x < 0 or x >= M or y < 0 or y >= N:
        return False
    return True

def findSum(x, y):
    global board, ans
    max_total = 0
    for i in range(len(blocks)):
        temp_sum = board[y][x]
        for (dx, dy) in blocks[i]:
            tx, ty = x + dx, y + dy
            if isRoad(tx, ty):
                temp_sum += board[ty][tx]
        max_total = max(temp_sum, max_total)

    if max_total > ans:
        ans = max_total

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
blocks = (
    ((1, 0), (2, 0), (3, 0)),
    ((0, 1), (0, 2), (0, 3)),

    ((0, 1), (1, 0), (1, 1)),

    ((0, 1), (0, 2), (1, 2)),
    ((1, 0), (1, -1), (1, -2)),
    ((1, 0), (2, 0), (2, -1)),
    ((0, 1), (1, 1), (2, 1)),
    ((1, 0), (1, 1), (1, 2)),
    ((1, 0), (0, 1), (0, 2)),
    ((1, 0), (2, 0), (0, 1)),
    ((1, 0), (2, 0), (2, 1)),

    ((0, 1), (1, 1), (1, 2)),
    ((0, 1), (1, 0), (-1, 1)),
    ((1, 0), (1, -1), (0, 1)),
    ((1, 0), (1, 1), (2, 1)),

    ((1, 0), (2, 0), (1, 1)),
    ((0, 1), (1, 1), (0, 2)),
    ((1, -1), (1, 0), (2, 0)),
    ((1, 0), (1, -1), (1, 1))
)
ans = 0

for y in range(N):
    for x in range(M):
        findSum(x, y)

print(ans)

처음에 대칭이 있는지 모르고 ^^ 회전만 시켰다가 틀리고,

오타 있어서 틀렸습니다.

 

후 ..

 

문제를 잘 읽도록 ..!