Search
Duplicate

나무 재테크

주차
0
문제번호
16235
언어
Python
티어
골드
유형
구현
시뮬레이션
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

Memo

이 문제의 키 포인트 (개인적인 생각)

같은 공간에 나무가 여러개 있을 경우 처리하는 방법 → 3차원 리스트로 해결
봄에서 나이가 가장 적은 나무들 부터 양분을 섭취하게 하는 방법 → sorting으로 해결
봄에서 나무가 죽는 경우 처리하는 방법 → sorting이 되어 있는 상태이므로 뒤의 나무들은 조사할 필요도 없이 다 죽게 되므로 현재 위치부터 끝까지 나무를 지워버림. (del tree_info[i][j][k:])
봄에서 죽은 나무들을 여름에서 양분으로 바꾸는 방법 → 바로 윗 부분에서 죽은 나무들을 지워버리기 전에 queue에 튜플 형태로 나무의 좌표와 나이를 넣고, 여름에서 해당 정보들을 이용하여 양분으로 바꿈

Code

제출 날짜

@4/2/2021

메모리

210668 KB

시간

860 ms
import sys from collections import deque import copy dy = [-1, -1, -1, 0, 0, 1, 1, 1] dx = [-1, 0, 1, -1, 1, -1, 0, 1] def spring(tree_info, g_map, q): for i in range(1, len(tree_info)): for j in range(1, len(tree_info[i])): if (len(tree_info[i][j])): tree_info[i][j].sort() for k in range(len(tree_info[i][j])): age = tree_info[i][j][k] if (age <= g_map[i][j]): # 양분을 먹는다면 g_map[i][j] -= age tree_info[i][j][k] += 1 else: # 죽는다면 for l in range(k, len(tree_info[i][j])): q.append((i, j, tree_info[i][j][l])) del tree_info[i][j][k:] break def summer(q, g_map): while q: y, x, age = q.popleft() g_map[y][x] += (age // 2) def fall(tree_info, N): global dy, dx for i in range(1, len(tree_info)): for j in range(1, len(tree_info[i])): if not (len(tree_info[i][j])): continue for k in range(len(tree_info[i][j])): if not (tree_info[i][j][k] % 5): # 5의 배수이면 for l in range(len(dx)): ny = i + dy[l] nx = j + dx[l] if (ny <= 0 or ny > N or nx <= 0 or nx > N): continue tree_info[ny][nx].append(1) def winter(A, g_map): for i in range(1, len(g_map)): for j in range(1, len(g_map[i])): g_map[i][j] += A[i - 1][j] N, M, K = map(int, sys.stdin.readline().split()) g_map = [[5 for _ in range(N + 1)] for _ in range(N + 1)] A = [] tree_info = [[[] for _ in range(N + 1)] for _ in range(N + 1)] for i in range(N): A.append([0] + list(map(int, sys.stdin.readline().split()))) for i in range(M): li = list(map(int, sys.stdin.readline().split())) y, x, z = li[0], li[1], li[2] tree_info[y][x].append(z) q = deque() while (K): spring(tree_info, g_map, q) summer(q, g_map) fall(tree_info, N) winter(A, g_map) K-=1 ans = 0 for i in range(1, len(tree_info)): for j in range(1, len(tree_info[i])): ans += len(tree_info[i][j]) print(ans)
Python
복사