문제
input
첫째 줄에 N, M, K가 주어진다.
둘째 줄부터 N개의 줄에 A배열의 값이 주어진다. r번째 줄의 c번째 값은 A[r][c]이다.
다음 M개의 줄에는 상도가 심은 나무의 정보를 나타내는 세 정수 x, y, z가 주어진다. 처음 두 개의 정수는 나무의 위치 (x, y)를 의미하고, 마지막 정수는 그 나무의 나이를 의미한다.
제한
1 ≤ N ≤ 10
1 ≤ M ≤ N2
1 ≤ K ≤ 1,000
1 ≤ A[r][c] ≤ 100
1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10
입력으로 주어지는 나무의 위치는 모두 서로 다름
Python 3: 1.3 초
PyPy3: 1.3 초
output
첫째 줄에 K년이 지난 후 살아남은 나무의 수를 출력한다.
TODO
땅덩이 하나씩 체크하면서 해당 위치에 나무들 나이, 양분 비교
나무들은 나이 오름차순으로 정렬할것이므로 죽는 나무가 나오면 그 뒤 나무는 다 죽음
봄 + 여름
땅위치 x y
x,y에 나무 수 0<= k < n
나이 = tree[x][y][k]
if 땅 x y의 양분 - 나이 >= 0 :
땅 양분 -= 나이
나이 += 1
else :
break
for _ in range(k,n):
땅 양분 += tree[x][y].pop() // 2나무의 나이가 5의 배수이면 인접한 8개의 칸에 나이가 1인 나무 만들기
땅에 양분 추가하기
가을 + 겨울
땅 위치 x y
for 나무 in 땅에 위치한 나무:
if 나무 % 5 == 0:
8방에 appendleft(1살 나무) # 나이순
땅[x][y] += 양분 [x][y]CODE
from collections import deque
import sys
input = sys.stdin.readline
def spring():
global answer
for i in range(n):
for j in range(n):
len_t = len(t[i][j])
for k in range(len_t):
if t[i][j][k] <= no[i][j]:
no[i][j] -= t[i][j][k]
t[i][j][k] += 1
else:
for _ in range(k, len_t):
no[i][j] += t[i][j].pop() // 2
answer -= 1
break
def fall():
global answer
for i in range(n):
for j in range(n):
for k in t[i][j]:
if k % 5 == 0:
for l in range(8):
x = i + dx[l]
y = j + dy[l]
if 0 <= x < n and 0 <= y < n:
t[x][y].appendleft(1)
answer+=1
no[i][j] += s[i][j]
dx = [1, -1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, -1, 1, 1, -1, -1, 1]
n, m, k = map(int, input().split())
answer = m
s = []
t = [[deque() for _ in range(n)] for _ in range(n)]
no = [[5] * n for _ in range(n)]
for i in range(n):
s.append(list(map(int, input().split())))
for i in range(m):
x, y, z = map(int, input().split())
t[x - 1][y - 1].append(z)
for i in range(k):
spring()
fall()
print(answer)회고
문제 자체는 단순구현이나 시간 제한이 조금 아찔했다.
처음에는 tree의 위치를 기준으로 계산하였는데 나무수가 금방 N**2보다 커진다.
->그냥 땅덩이 다 돌자
: 땅덩이 그냥 다 도니깐 봄+여름 가을+겨울로 처리가 가능
입력으로 주어지는 나무의 위치는 모두 서로 다름이라는 조건은 입력에서 같은 위치에 있는 나무가 없다는 뜻으로 봄에 양분을 누가 먼저 먹을지 안정해줘도 된다는 힌트인데 저걸 모르고 처음에 계속 정렬했다.
-