16235번 - 나무 재테크

문제

16235번: 나무 재테크 (acmicpc.net)

16235번: 나무 재테크

풀이 1

이 문제에서는 두가지의 교훈을 얻을 수 있다.

1. "아기 상어" 문제에서 얻은 교훈과 마찬가지로, 일단 탐색은 모든 경우를 탐색하며 조건문으로 거르는 방식을 시도해본뒤, 시간 초과가 나면 그 다음에 미리 풀을 좁혀놓고 탐색하는 방법을 시도하자는 것이다. 즉, 일단 볼것도없이 행-열 탐색을 싹다 해버려야지, 미리 좌표를 뽑아놓고 반복문을 돌리지 말자는 것이다! 이 문제의 경우, 한 곳에 나무가 "아주"많을 수 있기 때문에, 미리 좌표를 뽑아놓고, 또 그 좌표에 대한 연산을 추가해줬다 빼줬다 하는 방식은 그저 연산량만 쓸데없이 늘리는 접근법이다. 아무튼 제발 기억해두고 넘어가자.
2. 제한 사항으로 눈여겨볼 것은 크게 두가지 인데, 첫번째는 시간제한이 꽤나 빡빡하다는 것이며, 입력으로 주어지는 나무의 위치는 각각 고유하다는 것이다. 한 곳의 나무 배열에 새로 추가되는 나무는 항상 값이 '1'로 정해져 있으므로, 정렬이 따로 필요없음을 눈치챌 수 있다.

위 두가지만 빠르게 파악하면 쉽게 구현 가능한 문제이다.

from collections import deque

# 주변
surrounds = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

n,m,k = map(int,input().split())
fertility = [[0]*(n+1)]
for _ in range(n):
    li = [0] + list(map(int,input().split()))
    fertility.append(li)
board = [[5]*(n+1) for _ in range(n+1)]
trees = [[deque() for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    x,y,z = map(int,input().split())
    trees[x][y].append(z)

for year in range(1,k+1):
    for row in range(1,n+1):
        for col in range(1,n+1):
            if trees[row][col]:
                survivors = deque()
                while trees[row][col] and board[row][col] >= trees[row][col][0]:
                    board[row][col] -= trees[row][col][0]
                    survivors.append(trees[row][col].popleft() + 1)
                board[row][col] += sum(map(lambda x: x // 2, trees[row][col])) if trees[row][col] else 0
                trees[row][col] = survivors

    for row in range(1,n+1):
        for col in range(1,n+1):
            for tree in trees[row][col]:
                if tree % 5 == 0:
                    for dRow, dCol in surrounds:
                        nRow, nCol = row + dRow, col + dCol
                        if 1 <= nRow < n + 1 and 1 <= nCol < n + 1:
                            trees[nRow][nCol].appendleft(1)

    for row in range(1,n+1):
        for col in range(1,n+1):
            board[row][col] += fertility[row][col]

answer = 0
for row in range(1,n+1):
    for col in range(1,n+1):
        answer += len(trees[row][col])
print(answer)

풀이 2

위 풀이와 거의 같지만, 위 풀이 처럼 new_board를 따로 생성하여 사용하지 않는쪽이 100ms 정도 더 이득을 본다. 순수 구현 문제이며, 각 칸에 나무가 새로 들어올 때는 항상 나이가 1로 가장 어린 나무가 들어오므로 큐를 활용 가능하단 점을 유의하자.

from collections import deque

# N,NE,E,SE,S,SW,W,NW
dRow = [-1,-1,0,1,1,1,0,-1]
dCol = [0,1,1,1,0,-1,-1,-1]

N,M,K = map(int,input().split())
A = []
for _ in range(N):
    A.append(list(map(int,input().split())))
# 나무
board = [[deque() for col in range(N)] for row in range(N)]
# 양분
fertilizer = [[5]*N for _ in range(N)]
for _ in range(M):
    x,y,z = map(int,input().split())
    board[x-1][y-1].appendleft(z)

for _ in range(K):
    # 봄, 여름
    new_board = [[deque() for col in range(N)] for row in range(N)]
    for row in range(N):
        for col in range(N):
            while board[row][col]:
                if board[row][col][0] <= fertilizer[row][col]:
                    tree = board[row][col].popleft()
                    fertilizer[row][col] -= tree
                    new_board[row][col].append(tree+1)
                else:
                    break
            while board[row][col]:
                fertilizer[row][col] += (board[row][col].popleft())//2
    # 가을, 겨울
    for row in range(N):
        for col in range(N):
            while new_board[row][col]:
                tree = new_board[row][col].popleft()
                board[row][col].append(tree)
                if tree % 5 == 0:
                    for i in range(8):
                        nRow,nCol = row+dRow[i],col+dCol[i]
                        if 0 <= nRow < N and 0 <= nCol < N:
                            board[nRow][nCol].appendleft(1)
            fertilizer[row][col] += A[row][col]

answer = 0
for row in range(N):
    for col in range(N):
        answer += len(board[row][col])
print(answer)