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

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀
문제 👉 16235번: 나무 재테크

1. 문제

1. 양분의 정보가 들어있는 N*N크기의 땅에 M개의 나무를 심는다.
2. 가장 처음에 양분은 모든 칸에 5만큼 들어있다.
3. 나무는 한 칸을 차지하며, 한 칸에는 여러 나무가 심어져 있을 수도 있다.
4. 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 만약 한 칸에 여러 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 양분이 부족한 나무는 즉시 죽는다.
5. 여름에는 봄에 죽은 나무가 양분이 된다. 죽은 나무의 나이를 2로 나눈 값이 해당 칸에 양분으로 추가된다. (소수점 아래는 버림)
6. 가을에는 나이가 5의 배수인 나무가 인접한 8개의 칸에 나이가 1인 나무를 번식한다.
7. K년이 지난 후 살아남은 나무의 수를 출력한다.

2. 풀이

시뮬레이션을 이용한 문제 풀이

1. 나무의 위치와 개수를 list와 dictionary를 통해 저장한다.
2. 나무가 없으면 바로 양분을 추가한다.
3. 나무가 있으면 봄,여름,가을,겨울을 통해 나무를 업데이트한다.

3. 코드

from collections import deque, defaultdict
N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
tree = [[defaultdict(int) for _ in range(N)] for _ in range(N)]
arr = [[5] * N for _ in range(N)]
for _ in range(M):
    x, y, z = map(int, input().split())
    tree[x-1][y-1][z] += 1

d = [[-1,0], [1,0], [0,-1], [0,1], [-1,-1], [-1,1], [1,-1], [1,1]]

def solution():
    ret = 0

    def solve():
        global tree, arr, A
        temp = [[defaultdict(int) for _ in range(N)] for _ in range(N)]
        for x in range(N):
            for y in range(N):
                if not tree[x][y]: # 나무가 없는 경우
                    arr[x][y] += A[x][y] # 양분 추가
                    continue
                die, spread = 0, 0
                # 봄, 여름
                for age, num in sorted(tree[x][y].items()): # 나무 나이와 개수를 나이가 낮은 순서부터 추출
                    cnt = arr[x][y] // age
                    if cnt >= num:
                        arr[x][y] -= age * num
                        temp[x][y][age+1] += num
                        if (age+1) % 5 == 0:
                            spread += num
                    elif 1 <= cnt < num:
                        arr[x][y] -= age * cnt
                        temp[x][y][age+1] += cnt
                        die += (age//2) * (num-cnt)
                        if (age+1) % 5 == 0:
                            spread += cnt
                    else:
                        die += (age//2) * num
                # 가을
                if spread != 0:
                    for dx, dy in d:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < N and 0 <= ny < N:
                            temp[nx][ny][1] += spread
                # 겨울
                arr[x][y] += A[x][y] + die
        return temp

    for _ in range(K):
        global tree
        tree = solve()

    for x in range(N):
        for y in range(N):
            ret += sum(tree[x][y].values())

    return ret

print(solution())

• 결과 : 316 ms

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋