문제 이해
문제에 주어진대로 구현하면 되는 그냥 단순한 구현 문제이다.. 근데 시간초과 기준이 너무 짜다.......
시간초과가 많이 났다..ㅠ
아래는 문제다
봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
여름에는 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 어떤 칸 (r, c)와 인접한 칸은 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1) 이다. 상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.
겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.
K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하는 프로그램을 작성하시오.
문제 접근
봄, 여름, 가을, 겨울 순으로 순서를 나눠서 접근하면 된다.
따라서 처음에 봄함수, 여름함수, 가을함수, 겨울함수로 나누어 코딩했다.
하지만 아까 말했듯이 시간초과 기준이 짜기 때문에 합칠 수 있는 부분은 합쳐주었다.
문제 풀이
문제 풀이는 주석으로 남겨두겠다. 시간을 정말 잘 고려해야 한다.
깊은복사를 넣었었지만 시간때문에 다른 방법을 찾고, pop(i)가 시간복잡도 O(i)이기 때문에 이런 부분 역시 다른방법을 생각해야 한다.
import sys
from collections import deque
N, M, K = map(int, sys.stdin.readline().split())
eat = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 추가되는 양분
trees = [[[] for _ in range(N)] for i in range(N)]
for i in range(M):
x,y,age = map(int, sys.stdin.readline().split())
trees[x-1][y-1].append(age) #3차원리스트에 나이를 추가해줌
pan = [[5]*N for _ in range(N)] # 양분이 들어가있는 맵
die_trees = [] # 죽은 나무들의 좌표,나이를 저장할 리스트
dx = [0,0,1,1,1,-1,-1,-1] # 8방향
dy = [1,-1,0,-1,1,1,-1,0]
def spring(): # 봄
for i,line in enumerate(trees):
for j, ages in enumerate(line):
# 각 좌표에 존재하는 나무들의 나이 리스트를 오름차순으로 정렬한다.
# 어린 나무부터 양분을 먹게하기 위하여
trees[i][j].sort()
for k, age in enumerate(ages):
# 양분이 나이만큼 충분할 때
if age<=pan[i][j]:
pan[i][j]-=age
trees[i][j][k]+=1
# 양분이 나이만큼 충분하지 않을 때
else:
# 그 뒤에 있는 나무들 다 죽기 때문에 전부 죽은 나무리스트에 넣어준다.
for _ in range(k,len(trees[i][j])):
die_trees.append([i,j,trees[i][j].pop()])
break
def summer(): # 여름
while die_trees:
x,y,age = die_trees.pop()
pan[x][y]+=age//2 #양분화됨
def autumn(): # 가을, 겨울
for i,line in enumerate(trees):
for j, ages in enumerate(line):
for k, age in enumerate(ages):
if age%5==0 and age!=0: #나이가 5의 배수
for t in range(8): # 주위 8방향
ni=i+dx[t]
nj=j+dy[t]
if ni>=N or nj>=N or ni<0 or nj<0:
continue
# 맵에서 벗어나지 않는다면 새로운 나무 번식
trees[ni][nj].append(1)
pan[i][j] += eat[i][j] # 로봇이 양분 추가 - 겨울
for _ in range(K):
spring() # 함수실행
summer()
autumn()
result = 0 # 결과를 담을 변수
for i in range(N):
for j in range(N):
result += len(trees[i][j]) # 각 좌표의 나무들의 개수
print(result) # 결과출력제출 코드
import sys
from collections import deque
N, M, K = map(int, sys.stdin.readline().split())
eat = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 추가되는 양분
trees = [[[] for _ in range(N)] for i in range(N)]
for i in range(M):
x,y,age = map(int, sys.stdin.readline().split())
trees[x-1][y-1].append(age)
pan = [[5]*N for _ in range(N)]
die_trees = []
dx = [0,0,1,1,1,-1,-1,-1] # 8방향
dy = [1,-1,0,-1,1,1,-1,0]
def spring(): # 봄
for i,line in enumerate(trees):
for j, ages in enumerate(line):
trees[i][j].sort()
for k, age in enumerate(ages):
if age<=pan[i][j]:
pan[i][j]-=age
trees[i][j][k]+=1
else:
for _ in range(k,len(trees[i][j])):
die_trees.append([i,j,trees[i][j].pop()])
break
def summer(): # 여름
while die_trees:
x,y,age = die_trees.pop()
pan[x][y]+=age//2 #양분화됨
def autumn(): # 가을
for i,line in enumerate(trees):
for j, ages in enumerate(line):
for k, age in enumerate(ages):
if age%5==0 and age!=0: #나이가 5의 배수
for t in range(8):
ni=i+dx[t]
nj=j+dy[t]
if ni>=N or nj>=N or ni<0 or nj<0:
continue
trees[ni][nj].append(1)
pan[i][j] += eat[i][j] # 로봇이 양분 추가 winter
for _ in range(K):
spring()
summer()
autumn()
result = 0
for i in range(N):
for j in range(N):
result += len(trees[i][j])
print(result)