문제

BOJ 16235: 나무 재테크 https://www.acmicpc.net/problem/16235

풀이

조건

• 같은 1×1 크기의 칸에 여러 개의 나무가 심어져 있을 수도 있다.
• 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.
  • 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다.
  • 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
  • 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
• 여름에는 봄에 죽은 나무가 양분으로 변하게 된다.
  • 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
• 가을에는 나무가 번식한다.
  • 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
  • 땅을 벗어나는 칸에는 나무가 생기지 않는다.
• 겨울에는 모든 땅에 양분을 추가한다.

풀이 순서

• 생성할 배열
  • 위치별 나무들을 저장할 배열
  • 밭 상태를 저장할 배열
  • 죽은 나무들을 저장할 배열
  • 매년 줄 양분의 양을 저장한 배열
• deque을 사용해 나무들을 저장한다.
  • 이렇게 하면 정렬을 하지 않아도 된다.
• 죽은 나무들을 저장한 배열에서 해당 위치에 양분을 추가한다.
• 새로 태어난 나무들을 deque 앞으로 삽입한다.
  • 이렇게 해야 정렬을 하지 않아도 된다.

코드

Python

from collections import deque

n, m, k = map(int, input().split(' '))

# 양분 양 배열
a = [list(map(int, input().split(' '))) for _ in range(n)]
# 초기 밭 배열
graph = [[5] * n for _ in range(n)]
# 나무들 상태 저장할 배열
trees = [[deque() for _ in range(n)] for _ in range(n)]
# 위치별 죽은 나무들 저장할 배열
dead_trees = [[list() for _ in range(n)] for _ in range(n)]

# 입력받은 초기 나무 위치, 나이 저장
for _ in range(m):
    x, y, z = map(int, input().split(' '))
    trees[x - 1][y - 1].append(z)

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

# 봄, 여름 처리할 함수
def spring_summer():
    for i in range(n):
        for j in range(n):
            len_ = len(trees[i][j]) # 현재 위치에 있는 나무 총 개수
            # 현재 위치의 나무들 탐색
            for k in range(len_):
                # 나무가 죽는 경우
                if graph[i][j] < trees[i][j][k]:
                    # 죽는 나무들은 따로 저장
                    for _ in range(k, len_):
                        dead_trees[i][j].append(trees[i][j].pop())
                    break
                # 나무가 양분 먹고 성장하는 경우
                else:
                    graph[i][j] -= trees[i][j][k]
                    trees[i][j][k] += 1
    # 죽은 나무들 만큼 양분 저장
    for i in range(n):
        for j in range(n):
            while dead_trees[i][j]:
                graph[i][j] += dead_trees[i][j].pop() // 2

# 가을, 겨울 처리할 함수
def fall_winter():
    for i in range(n):
        for j in range(n):
            # 현재 위치의 나무들 탐색
            for k in range(len(trees[i][j])):
                # 현재 나무의 나이가 씨를 뿌릴 수 있는 상태인 경우
                if trees[i][j][k] % 5 == 0:
                    # 8방향에 씨 뿌림
                    for t in range(8):
                        nx = i + dx[t]
                        ny = j + dy[t]
                        # 범위 체크
                        if nx < 0 or nx >= n or ny < 0 or ny >= n:
                            continue
                        # 새로 태어난 나무들 앞으로 삽입
                        trees[nx][ny].appendleft(1)
            # 밭에 양분 추가
            graph[i][j] += a[i][j]


for i in range(k):
    spring_summer()
    fall_winter()

answer = 0
for i in range(n):
    for j in range(n):
        answer += len(trees[i][j])

print(answer)

정리

• 처음에는 dictionary를 사용해 위치마다 나무들을 저장했다.
• 성장한 나무와 죽은 나무를 솎아내고 결과를 따로 dictionary에 다시 저장하는 부분에서 시간 초과가 났다.
• deque에서 값을 뽑아내는 과정의 시간복잡도는 O(1)이다.