백준: 16235 나무 재테크

문제

16235번: 나무 재테크

 

문제 풀이

 시뮬레이션 문제로 문제 요구사항에 따라 그대로 구현하면 된다. 나무들은 계절에 따라 다음과 같이 나이가 변화하게 된다. 따라서 각 계절에 따른 로직을 구현하고 `K` 만큼 반복하면 답을 찾을 수 있다.

 

• 봄
  • 나무 나이 만큼의 양분을 먹고 나이가 1 증가한다.
  • 자신이 위치한 곳의 양분만 먹을 수 있다.
  • 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 섭취한다.
  • 나무의 나이만큼 양분을 먹지 못하면 죽게 된다.
• 여름
  • 봄에 죽은 나무가 양분으로 변하게 된다.
  • 죽은 나무의 나이를 2로 나눈 값이 나무가 있던 칸의 양분으로 추가된다.
• 가을
  • 나무가 8 방향으로 번식을 하며, 번식 가능한 나무는 나이가 5의 배수여야 한다.
  • NxN 크기를 벗어날 경우 번식을 하지 않는다.
• 겨울
  • 로봇이 돌아다니며, 초기에 주어진 값에 따라 양분을 추가한다.

 즉 봄에 나이가 어린 나무 부터 양분을 섭취하고, 더 이상 양분을 섭취할 수 없는 경우 나머지는 죽은 나무가 되므로 여름의 로직을 실행하면 된다. 이후에 가을, 겨울의 로직은 간단하다.

 

코드

from sys import stdin


def spring_summer():
    for x in range(n):
        for y in range(n):
            if not tree[x][y]:
                continue

            # 어린 나무 부터 순서대로 정렬.
            tree[x][y].sort()

            for idx, cur_age in enumerate(tree[x][y]):
                # 봄
                if cur_age <= graph[x][y]:
                    graph[x][y] -= cur_age
                    tree[x][y][idx] += 1
                # 여름
                else:
                    # 죽은 나무의 양분을 저장함.
                    graph[x][y] += (sum([(die // 2) for die in tree[x][y][idx:]]))
                    # 뒤의 나무들은 죽은 나무 이므로 값을 날림.
                    tree[x][y] = tree[x][y][:idx]
                    break


def fall():
    for x in range(n):
        for y in range(n):
            cnt = 0
            if not tree[x][y]:
                continue

            for cur_age in tree[x][y]:
                # 5의 배수일 경우만
                if cur_age % 5 == 0:
                    cnt += 1
            if cnt:
                for dx, dy in dirs:
                    next_x, next_y = x + dx, y + dy
                    if 0 <= next_x < n and 0 <= next_y < n:
                        for _ in range(cnt):
                            tree[next_x][next_y].append(1)


def winter():
    for x in range(n):
        for y in range(n):
            graph[x][y] += nutrient[x][y]


if __name__ == '__main__':
    dirs = ((-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1))
    n, m, k = map(int, stdin.readline().split())
    # 겨울에 추가할 양분 값.
    nutrient = [list(map(int, stdin.readline().split())) for _ in range(n)]
    # 모든 칸에 양분은 5씩 들어 있음
    graph = [[5] * n for _ in range(n)]
    tree = [[[] for _ in range(n)] for _ in range(n)]

    for _ in range(m):
        i, j, age = map(int, stdin.readline().split())
        tree[i - 1][j - 1].append(age)

    # k만큼 반복문을 돌며, 봄, 여름, 가을, 겨울을 시뮬레이션 하면 됨.
    for _ in range(k):
        spring_summer()
        fall()
        winter()

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

    print(answer)

 파이썬으로는 해당 코드가 시간 초과가 발생하여 PyPy3로 제출하였다. 아마 `sort`와 `indexing`하는 오버헤드로 인해 시간 초과가 발생하는 것 같다.