[백준 16235번] 나무 재테크 - python

문제 링크

https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

풀이

구현 문제, pypy3 으로 통과

 

한동안 구현문제를 풀다가 어디서 잘못된건지 디버깅 하느라 시간이 많이 걸렸는데, 

기능 별로 함수로 쪼개서 구현하고 디버깅하면 훨씬 간단해지는 것 같다.

한 함수 안에서도 너무 많은 걸 하려고 하지 말고, 다른 함수 쪼개면 어디서 틀렸는지 잡기가 쉬워지는 듯 하다. 

 

이 문제는 문제에서 시키는 그대로 구현만 하면 되었다. 

food 에는 위치별 양분, graph라는 3차원 배열에는 위치별 나무 리스트가 들어가있다. 

1. spring + summer 

각 위치별 나무에 대해 어린 나무 순으로 정렬하고, 차례대로 자신의 나이 만큼 양분을 먹는다. 

이 때, 양분이 모자라면 dead라는 이차원 배열의 현재 위치에 죽은 나이 // 2 를 더한다. -> 여름 때 사용할 것 

+ 나무들에 대해서 바로 양분의 양을 줄여줬는데, 죽은 나무는 양분을 먹지 않고 죽기 때문에 이전 양분까지의 양분의 양을 유지해야한다. 

양분을 먹을 수 있으면 현재 위치의 리스트에 나이가 1인 나무를 삽입시켜준다. 

남은 양분의 양을 갱신한다. 

 

아까 dead에 저장된 값들을 food에 더한다. 

 

2. fall 

각 위치별 나무들에 대해 5의 배수이면 8방향의 리스트에 나이가 1인 나무들을 삽입시켜준다. 

 

3. winter 

food 배열에 A 배열에 적힌 값을 더해준다. 

# 봄 + 여름 
def spring():
    dead =[ [0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            tree = graph[i][j]
            f = food[i][j]
            tree.sort()
            tmp = []
            for t in tree:
                nf = f - t
                if nf < 0 :
                    dead[i][j] += t // 2
                else :
                    f = nf
                    tmp.append(t+1)

            graph[i][j] = tmp
            food[i][j] = f

    # summer
    for i in range(n):
        for j in range(n):
            food[i][j] += dead[i][j]

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

# 가을 
def fall():

    for i in range(n):
        for j in range(n):

            for t in graph[i][j]:
                if t % 5 == 0:
                    for h in range(8):
                        nx = i + dx[h]
                        ny = j + dy[h]

                        if nx < 0 or nx >= n or ny < 0 or ny >= n :
                            continue

                        graph[nx][ny].append(1)

# 겨울 
def winter():
    for i in range(n):
        for j in range(n):
            food[i][j] += A[i][j]

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

A = []

for _ in range(n):
    A.append(list(map(int,input().split())))

# 현재 양분 
food = [[5] * n for _ in range(n)]
# 심겨진 나무 
graph = [ [[] for _ in range(n)] for _ in range(n) ]

for _ in range(m):
    x, y, z = map(int,input().split())
    graph[x-1][y-1].append(z)

for _ in range(k):
    spring()

    fall()

    winter()

ans = 0

for i in range(n):
    for j in range(n):
        ans += len(graph[i][j])

print(ans)