[백준] 16235번 나무 재테크
문제 링크
https://www.acmicpc.net/problem/16235
문제 설명
- 몇 년 키울지, 초기에 심을 나무 정보, 매년 추가될 양분 정보가 주어짐
- 봄에는 나이 순으로 양분을 먹고 나이를 먹음
- 여름에는 양분을 먹지 못한 나무가 죽음
- 가을에는 나무들이 번식해 1살 나무가 추가됨
- 겨울에는 양분을 추가해줌
풀이
- 그대로 구현하면 되지만 좌표별 나무의 나이순 정렬을 유지하는 것이 중요하다
- 추가될 나무가 1살이라 항상 최솟값이기 때문에 deque를 사용해 appendleft 해준다
- 이렇게 하면 특정 좌표의 나무를 탐색하고 정렬을 유지하는데 O(N)으로 가능하다
- N : 특정 좌표의 나무 개수
후기
- 처음에 heapq로 정렬을 유지했는데 시간초과 났다
- deque에서 양분에 부족할 때 죽는 나무를 바로 양분에 더해줘서 헤맸다
- 양분 값이 달라져서 이후에 죽는 나무가 달라진다
코드
def spring_summer():
for i in range(n):
for j in range(n):
new_tree = deque()
while tree[i][j]:
curr = tree[i][j].popleft()
if food[i][j] >= curr:
food[i][j] -= curr
new_tree.append(curr + 1)
else:
tree[i][j].appendleft(curr)
break
while tree[i][j]:
curr = tree[i][j].popleft()
food[i][j] += curr // 2
tree[i][j] = new_tree
def fall():
for i in range(n):
for j in range(n):
for y in tree[i][j]:
if y % 5 == 0:
append_tree(i, j)
def append_tree(cy, cx):
dy = [0,0,-1,1,-1,1,-1,1]
dx = [1,-1,0,0,-1,1,1,-1]
for d in range(8):
ny, nx = cy + dy[d], cx + dx[d]
if 0 <= ny < n and 0 <= nx < n:
tree[ny][nx].appendleft(1)
def winter():
for i in range(n):
for j in range(n):
food[i][j] += added_food[i][j]
def get_answer():
answer = 0
for i in range(n):
for j in range(n):
answer += len(tree[i][j])
return answer
# init
from collections import deque
import sys, heapq
read = sys.stdin.readline
n, m, k = map(int, read().split())
added_food = [list(map(int, read().split())) for _ in range(n)]
food = [[5]*n for _ in range(n)]
tree = [[deque() for _ in range(n)] for _ in range(n)]
inputs = [list(map(int, read().split())) for _ in range(m)]
for y, x, year in inputs:
tree[y-1][x-1].append(year)
# start
for y in range(k):
spring_summer()
fall()
winter()
print(get_answer())
Author And Source
이 문제에 관하여([백준] 16235번 나무 재테크), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-16235번-나무-재테크
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 그대로 구현하면 되지만 좌표별 나무의 나이순 정렬을 유지하는 것이 중요하다
- 추가될 나무가 1살이라 항상 최솟값이기 때문에 deque를 사용해 appendleft 해준다
- 이렇게 하면 특정 좌표의 나무를 탐색하고 정렬을 유지하는데 O(N)으로 가능하다
- N : 특정 좌표의 나무 개수
후기
- 처음에 heapq로 정렬을 유지했는데 시간초과 났다
- deque에서 양분에 부족할 때 죽는 나무를 바로 양분에 더해줘서 헤맸다
- 양분 값이 달라져서 이후에 죽는 나무가 달라진다
코드
def spring_summer():
for i in range(n):
for j in range(n):
new_tree = deque()
while tree[i][j]:
curr = tree[i][j].popleft()
if food[i][j] >= curr:
food[i][j] -= curr
new_tree.append(curr + 1)
else:
tree[i][j].appendleft(curr)
break
while tree[i][j]:
curr = tree[i][j].popleft()
food[i][j] += curr // 2
tree[i][j] = new_tree
def fall():
for i in range(n):
for j in range(n):
for y in tree[i][j]:
if y % 5 == 0:
append_tree(i, j)
def append_tree(cy, cx):
dy = [0,0,-1,1,-1,1,-1,1]
dx = [1,-1,0,0,-1,1,1,-1]
for d in range(8):
ny, nx = cy + dy[d], cx + dx[d]
if 0 <= ny < n and 0 <= nx < n:
tree[ny][nx].appendleft(1)
def winter():
for i in range(n):
for j in range(n):
food[i][j] += added_food[i][j]
def get_answer():
answer = 0
for i in range(n):
for j in range(n):
answer += len(tree[i][j])
return answer
# init
from collections import deque
import sys, heapq
read = sys.stdin.readline
n, m, k = map(int, read().split())
added_food = [list(map(int, read().split())) for _ in range(n)]
food = [[5]*n for _ in range(n)]
tree = [[deque() for _ in range(n)] for _ in range(n)]
inputs = [list(map(int, read().split())) for _ in range(m)]
for y, x, year in inputs:
tree[y-1][x-1].append(year)
# start
for y in range(k):
spring_summer()
fall()
winter()
print(get_answer())
Author And Source
이 문제에 관하여([백준] 16235번 나무 재테크), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-16235번-나무-재테크
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
def spring_summer():
for i in range(n):
for j in range(n):
new_tree = deque()
while tree[i][j]:
curr = tree[i][j].popleft()
if food[i][j] >= curr:
food[i][j] -= curr
new_tree.append(curr + 1)
else:
tree[i][j].appendleft(curr)
break
while tree[i][j]:
curr = tree[i][j].popleft()
food[i][j] += curr // 2
tree[i][j] = new_tree
def fall():
for i in range(n):
for j in range(n):
for y in tree[i][j]:
if y % 5 == 0:
append_tree(i, j)
def append_tree(cy, cx):
dy = [0,0,-1,1,-1,1,-1,1]
dx = [1,-1,0,0,-1,1,1,-1]
for d in range(8):
ny, nx = cy + dy[d], cx + dx[d]
if 0 <= ny < n and 0 <= nx < n:
tree[ny][nx].appendleft(1)
def winter():
for i in range(n):
for j in range(n):
food[i][j] += added_food[i][j]
def get_answer():
answer = 0
for i in range(n):
for j in range(n):
answer += len(tree[i][j])
return answer
# init
from collections import deque
import sys, heapq
read = sys.stdin.readline
n, m, k = map(int, read().split())
added_food = [list(map(int, read().split())) for _ in range(n)]
food = [[5]*n for _ in range(n)]
tree = [[deque() for _ in range(n)] for _ in range(n)]
inputs = [list(map(int, read().split())) for _ in range(m)]
for y, x, year in inputs:
tree[y-1][x-1].append(year)
# start
for y in range(k):
spring_summer()
fall()
winter()
print(get_answer())
Author And Source
이 문제에 관하여([백준] 16235번 나무 재테크), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-16235번-나무-재테크저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)