문제 링크
문제 설명
N*N크기의 땅이 있다. 땅 (r,c)는 위에서부터 r칸, 왼쪽에서부터 c칸 떨어진 1*1 정사각형 크기의 땅이다. (1<= r,c <= N) 각 칸에는 양분이 주어진다. M개의 나무를 땅에 심어서 나무 재테크를 하려고 한다.
사계절동안
- 봄: 각각의 나무가 나이만큼 양분을 먹는다
-> 한칸에 여러 나무가 있으면 어린 나무부터 양분을 섭취하고, 양분이 부족해서 못먹는 나무는 즉사 - 여름: 봄에 죽은 나무가 양분이 된다
-> 나이//2만큼 ++ - 가을 : 나이가 5의 배수인 나무가 번식한다
-> 인접 8칸에 나이 1인 나무가 생성 - 겨울 : 로봇이 돌아다니면서 땅에 양분을 추가한다
-> (r,c) += A[r][c]
K년 뒤, 살아남은 나무의 개수는?
문제 풀이
그냥 시키는 대로 하면 되는 구현 문젠데 디버깅이 빡세서,, 틀린 부분 찾는데 애먹었다.
코드 설명부터 하자면,
-
입력받기
A[i][j] : (i, j)에 매년 추가될 양분을 저장하는 리스트 count = M : 총 나무의 수 -> 초기값은 M이다 food[i][j] :(i, j)에 현재 있는 양분의 양을 저장하는 리스트 trees[i][j] : (i, j)에 심어진 나무들의 나이를 저장하는 리스트에 맞게 입력을 저장한다. 어차피 새로 번식하는 나무는 죄다 1살이기 때문에 처음에 입력받을때 한번 정렬해준다.
-
봄/여름
각 칸에 있는 나무에 대해서 나이만큼 양분을 먹을 수 있는지 검사하고,
가능하면 1. 해당 칸의 양분 나이만큼 줄이기 2. 나무의 나이 += 1
불가능하면 1. 해당 나무부터 나머지 나무를 양분으로 만든다(여름) 2. 리스트에서 죽은 나무들 지우기
for i in range(N):
for j in range(N):
if trees[i][j]:
# 나이만큼 양분 먹기
for t in range(len(trees[i][j])):
if food[i][j] - trees[i][j][t] < 0:
while t < len(trees[i][j]):
food[i][j] += (trees[i][j].pop()//2)
count -= 1
break
else:
food[i][j] -= trees[i][j][t]
trees[i][j][t] += 1- 가을
나이가 5의 배수인 나무들에 대해서 인접한 8칸에 대해 나이가 1인 나무를 번식한다. 정렬된 배열을 유지하기 위해서 insert()로 나무 리스트의 제일 앞에 삽입해준다.
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
dy = [-1, -1, -1, 0, 0, 1, 1, 1]
# 가을
for i in range(N):
for j in range(N):
if trees[i][j]:
for t in trees[i][j]:
if t%5 == 0:
# 8방향으로 번식
for k in range(8):
nx, ny = i+dx[k], j+dy[k]
# 8방향으로 번식
if nx < 0 or nx >= N or ny < 0 or ny >= N:
continue
else:
trees[nx][ny].insert(0,1)
count += 1- 겨울
입력받은 대로 양분을 공급!
for i in range(N):
for j in range(N):
food[i][j] += A[i][j]시도 1
처음에는 문제를 그냥 슥 읽고, 어린 나무부터 양분을 섭취한다길래 heap을 사용해서 구현했다.
import sys
import heapq
input = sys.stdin.readline
N, M, K = map(int, input().split())
A = [] # 매년 추가될 양분의 양 저장
count = M # 총 나무의 수
for i in range(N):
A.append(list(map(int, input().split())))
food = [[5]*N for _ in range(N)] #food[i][j]: (i.j)에 저장된 양분의 양
trees = [[[] for _ in range(N)] for _ in range(N)] # trees[i][j]: (i,j)에 있는 나무 나이 리스트
for i in range(M):
x, y, z = map(int, input().split())
heapq.heappush(trees[x-1][y-1], z)
for year in range(K):
# 봄 & 여름
for i in range(N):
for j in range(N):
if trees[i][j]:
# 나이만큼 양분 먹기
for t in range(len(trees[i][j])):
age = trees[i][j][t]
if food[i][j] - age < 0:
# 나이만큼 먹을 양분이 없으면
tree = list(trees[i][j])
del_tree = tree[t:] # 죽은 나무 -> 양분으로
for d in del_tree:
food[i][j] += d//2
pos_tree = tree[:t] # 살아남은 나무
trees[i][j] = pos_tree
count -= len(del_tree)
break
else:
food[i][j] -= age
trees[i][j][t] += 1
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
dy = [-1, -1, -1, 0, 0, 1, 1, 1]
# 가을
for i in range(N):
for j in range(N):
if trees[i][j]:
for t in trees[i][j]:
if t%5 == 0:
for k in range(8):
nx, ny = i+dx[k], j+dy[k]
# 8방향으로 번식
if nx < 0 or nx >= N or ny < 0 or ny >= N:
continue
else:
trees[nx][ny].insert(0,1)
count += 1
# 겨율
for i in range(N):
for j in range(N):
food[i][j] += A[i][j]
print(count)-> 얘도 pypy3으로 통과되기는 하는데 ,, 생각해보니까 어차피 새로 들어오는 나무는 죄다 1살이라 처음에 입력받을때만 한번 정렬해주면 된다.
시도 2
그래서 그냥 list를 이용해서 구현하고, 새로 들어오는 나무는 insert()를 이용해서 삽입했다.
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
A = [] # 매년 추가될 양분의 양 저장
count = M # 총 나무의 수
for i in range(N):
A.append(list(map(int, input().split())))
food = [[5]*N for _ in range(N)] #food[i][j]: (i.j)에 저장된 양분의 양
trees = [[[] for _ in range(N)] for _ in range(N)] # trees[i][j]: (i,j)에 있는 나무 나이 리스트
for i in range(M):
x, y, z = map(int, input().split())
trees[x-1][y-1].append(z)
for i in range(N):
for j in range(N):
trees[i][j].sort()
for year in range(K):
# 봄 & 여름
for i in range(N):
for j in range(N):
if trees[i][j]:
# 나이만큼 양분 먹기
for t in range(len(trees[i][j])):
age = trees[i][j][t]
if food[i][j] - age < 0:
# 나이만큼 먹을 양분이 없으면
del_tree = trees[i][j][t:] # 죽은 나무 -> 양분으로
for d in del_tree:
food[i][j] += d//2
trees[i][j] = trees[i][j][:t]
count -= len(del_tree)
break
else:
food[i][j] -= age
trees[i][j][t] += 1
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
dy = [-1, -1, -1, 0, 0, 1, 1, 1]
# 가을
for i in range(N):
for j in range(N):
if trees[i][j]:
for t in trees[i][j]:
if t%5 == 0:
for k in range(8):
nx, ny = i+dx[k], j+dy[k]
# 8방향으로 번식
if nx < 0 or nx >= N or ny < 0 or ny >= N:
continue
else:
trees[nx][ny].insert(0,1)
count += 1
# 겨율
for i in range(N):
for j in range(N):
food[i][j] += A[i][j]
print(count)이건 구글링하다 본 코든데 훨씬 간단해서..
봄에 해당 칸에 양분이 부족한 경우를 구현한 부분이다.
if food[i][j] - trees[i][j][t] < 0:
# 나이만큼 먹을 양분이 없으면
tree = list(trees[i][j])
del_tree = tree[t:] # 죽은 나무 -> 양분으로
for d in del_tree:
food[i][j] += d//2
pos_tree = tree[:t] # 살아남은 나무
trees[i][j] = pos_tree
count -= len(del_tree)break나는 얘를 또 살아남은 나무와 죽은 나무로 슬라이싱해서 계산했다. 굳이 이럴 필요 없이 바로 pop해주면 간단 이지
if food[i][j] - trees[i][j][t] < 0:
while t < len(trees[i][j]):
food[i][j] += (trees[i][j].pop()//2)
count -= 1
break
Hongik CE