[백준 16235번] 나무 재테크(파이썬)

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

16235번: 나무 재테크

봄 여름 가을 겨울대로

문제에서 주어진 걸 적어보면

 

봄

나이가 어린 나무부터 양분을 먹음

나이만큼 양분을 먹고, 양분 못먹으면 죽음

 

여름

봄에 죽은 나무가 양분이 된다.

이 때, 죽은 나무//2만큼 양분이 생성

 

가을

나무나이가 5의 배수일 때 번식.

인접한 칸에 1인 나무 생성.

 

겨울

각 토양에 양분증가.

입력받았던 걸로 더 추가

 

첫번째부터 난관에 봉착합니다.

봄 여름 가을 겨울 각각 구현은 고사하고

어떻게 토양과 나무를 받을지 난감해집니다.

한 리스트안에

토양과 나무를 한번에 받을까하다가

그러다가 스스로 너무 복잡해져서

나중에 디버깅이 힘들다고 생각했습니다.

그래서 아예, 토양과 나무

각각의 리스트를 분리해서 구했습니다.

tree=[[[]for _ in range(N)]for _ in range(N)]

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

 

나무같은 경우에는

이런 식으로 리스트를 구현하여

각각의 칸에

나무가 어떤 나이로 자리하고 있는지를 구현했습니다.

먼저 봄입니다.

현재 나무자리에

3 1 4 5 가 있다고 가정했습니다.

우선, 어린순으로 해야하니

sort를 시켜줍니다.

그리고 맨 앞부터 양분을 먹여줍니다.

계속 양분을 먹다가

t=2, 즉, 나이가 4인 지점에 오면

더 이상 양분을 먹지 못합니다.

t=2와 그 뒤에있는 나무까지

전부 pop을 시킵니다.

그 다음 여름.

지운 나무나이//2만큼을

현재 양분에 더해줍니다.

저는 코드를 구현할 때

봄에서 나무를 죽이면서

바로 여름을 구현했습니다.

 

그 다음 가을.

가을부터는 간단합니다.

현재 지점의 나무를 하나씩 보되

나이가 5의 배수가 있는지 확인.

저는

(나무)%5==0 and (나무)>0

이렇게 구현했습니다.

나무가 0인 경우에도

나무%5==0이 되기 떄문이죠.

 

마지막 겨울

처음에 입력했던 걸

양분에 더해집니다.

문제를 잘못읽으면

'처음 입력할 때

양분값을 받는거구나'

하실 수 있습니다.

그러다가 겨울 읽다가

'입력받은 값?

어디서 입력받는다는거지??'

하다가 다시 문제를 읽어보니

'처음에 양분이 5로 전부 초기화'

라는 걸 보고

'겨울에 처음에 입력받은 걸 더해주는 거구나'

라는 걸 알았습니다.

 

 

# 백준 16235번 나무 재태크
from copy import deepcopy

N, M, K = map(int, input().split())

A = [[5] * N for _ in range(N)]
put = [list(map(int, input().split())) for _ in range(N)]

tree = [[[] for _ in range(N)] for _ in range(N)]

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

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

year = 0
while year < K:
    # 봄-->나무 양분 먹어야함(나이 어린 순서부터)
    for x in range(N):
        for y in range(N):
            if tree[x][y]:
                tree[x][y].sort()
                now_tree_num = len(tree[x][y])
                t = 0
                # 양분만큼 나무의 나이를 증가
                while t < now_tree_num:
                    if A[x][y] > 0:
                        A[x][y] -= tree[x][y][t]
                        if A[x][y] < 0:
                            A[x][y] += tree[x][y][t]
                            break
                        tree[x][y][t] += 1
                    else:
                        break
                    t += 1
                # 만약에 중간에 양분이 없다면 그 뒤의 나무는 죽는다
                # 바로 여름-->죽은 나무가 양분이 된다
                # 양분은 나이를 2 나눈 값의 정수
                if not t == now_tree_num:
                    index = t
                    while t < now_tree_num:
                        death = tree[x][y].pop(index)
                        A[x][y] += death // 2
                        t += 1

    # 가을-->나무번식
    # 나무의 나이가 5의 배수일 때, 인접한 나무에 1인 나무가 생성
    for x in range(N):
        for y in range(N):
            if tree[x][y]:
                now_tree_num = len(tree[x][y])
                for now in range(now_tree_num):
                    if tree[x][y][now] % 5 == 0 and tree[x][y][now] > 0:
                        for d in range(8):
                            nx = x + dx[d]
                            ny = y + dy[d]
                            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                                continue
                            tree[nx][ny].append(1)

    # print(A)
    # 겨울-->모든 칸에 양분추가
    for x in range(N):
        for y in range(N):
            A[x][y] += put[x][y]
    year += 1

# 남아있는 나무수 구함

rest_tree = 0
for x in range(N):
    for y in range(N):
        if tree[x][y]:
            rest_tree += len(tree[x][y])
print(rest_tree)

 

pypy3로 제출했습니다.

저는 봄 여름 가을 겨울을 구할 때

각각을 구현하면서

나무 토양이 맞게 되었는지

print로 계속 확인했습니다.

 

https://tmdrl5779.tistory.com/147

[백준] 16235번 (python 파이썬)

시간초과에 대한 부분이 있어서

다른 분의 코드를 참고했습니다.

이분 같은 경우에는

dead tree라는 리스트를 받아서

죽은 나무를 따로 구하셨네요.

봄을 구할 때,

양분이 없으면 바로 dead tree에 받아서

바로 여름의 양분추가를 수행하는 식입니다.

이렇게 따로 죽은 나무의 리스트를 받는 것도

좋은 방법이 될 수 있겠네요 ^^