이번 문제는 삼성 기출 문제로 문제에서 주어진 조건대로 구현하여 해결하였다. 데이터를 관리하는 형태를 정하는 것이 조금 고민 되었는데, 나무의 경우에는 3차원 리스트를 이용하여 한칸의 땅에 나무가 여러그루 있는 것을 구현했고, 영양분의 정보를 2차원 리스트로 따로 관리하였다. 그리고 로봇이 양분을 추가하는 양에 해당하는 정보도 따로 리스트로 관리하였다. 구현이 복잡하게 느껴질수록 함수로 각 기능을 잘라서 구현하면 조금 정리가 잘 된다는 느낌이 들어서 계절별로 일어나는 일들을 함수로 정의하였다. 여름의 경우에는 봄에서 사라진 나무들의 나이가 양분으로 저장되기 때문에 봄과 여름을 함께 구현하였다.

• spring_summer:
  각 칸의 작은 나무부터 양분을 먹고 자람. -> 양분 부족 시, 못먹은 나무들을 2등분하여 양분에 더함. -> 양분을 못먹은 나무의 뒤에 나무들을 버림.
• fall:
  나무의 8방향을 탐색하여 범위 내에 들어갈 경우 1크기의 나무를 추가함.
• winter:
  로봇으로 주어진만큼의 양분을 더해줌.

반복문이 많이 사용되어 시간복잡도가 터질까 걱정도 하였지만, n의 최대가 10이고, k의 최대가 1000이기 때문에 시간은 널널했다.

• n, m, k를 입력받는다.
• a를 입력받는다.
• trees를 3차원 리스트로 선언한다.
• m번 반복하는 for문을 돌린다.
  -> x, y, z를 입력받는다.
  -> trees[x-1][y-1]에 z를 넣는다.
• 양분의 정보에 해당하는 리스트 nutrients를 n*n 크기에 5로 가득 채워 선언한다.
• dy, dx를 8방향으로 저장한다.
• spring_summer 함수를 선언한다.
  -> n번 반복하는 i에 대한 for문을 돌린다.
  --> n번 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 trees[i][j]가 빈 리스트가 아닐 경우,
  ----> trees[i][j]를 오름차순 정렬한다.
  ----> trees[i][j]의 길이만큼 반복하는 l에 대한 for문을 돌린다.
  -----> 만약 nutrients[i][j]가 trees[i][j][l]보다 크거나 같을 경우,
  ------> nutrients[i][j]를 trees[i][j][l]만큼 감소시킨다.
  ------> trees[i][j][l]을 1 증가시킨다.
  -----> 그 외의 경우,
  ------> l부터 trees[i][j]의 길이만큼 반복하는 o에 대한 for문을 돌린다.
  -------> nutrients[i][j]에 trees[i][j][o]//2를 더한다.
  ------> trees[i][j]를 trees[i][j][:l]로 갱신한다.
  ------> 반복문을 종료한다.
• fall 함수를 선언한다.
  -> n번 반복하는 i에 대한 for문을 돌린다.
  --> n번 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 trees[i][j]가 빈 리스트가 아닐 경우,
  ----> trees[i][j]의 길이만큼 반복하는 l에 대한 for문을 돌린다.
  -----> 만약 trees[i][j][l]이 5로 나눠 떨어질 경우,
  ------> 8번 반복하는 d에 대한 for문을 돌린다.
  -------> ny, nx를 i+dy[d], j+dx[d]로 선언한다.
  -------> 만약 ny, nx가 0 이상, n 미만일 경우,
  --------> trees[ny][nx]에 1을 넣는다.
• winter 함수를 선언한다.
  -> n번 반복하는 i에 대한 for문을 돌린다.
  --> n번 반복하는 j에 대한 for문을 돌린다.
  ---> nutrients[i][j]에 a[i][j]를 더한다.
• k번 반복하는 for문을 돌린다.
  -> spring_summer() 함수를 호출한다.
  -> fall() 함수를 호출한다.
  -> winter() 함수를 호출한다.
• 정답을 저장할 변수 answer를 0으로 선언한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> n번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 trees[i][j]가 빈 리스트가 아닐 경우,
  ---> answer에 trees[i][j]의 길이를 더한다.
• answer를 출력한다.

Code

n, m, k=map(int, input().split())
a=[list(map(int, input().split())) for _ in range(n)]
trees=[[[] for _ in range(n)] for _ in range(n)]
for _ in range(m):
    x, y, z=map(int, input().split())
    trees[x-1][y-1].append(z)
nutrients=[[5 for _ in range(n)] for _ in range(n)]
dy, dx=[-1, -1, 0, 1, 1, 1, 0, -1], [0, 1, 1, 1, 0, -1, -1, -1]
def spring_summer():
    for i in range(n):
        for j in range(n):
            if trees[i][j]:
                trees[i][j].sort()
                for l in range(len(trees[i][j])):
                    if nutrients[i][j]>=trees[i][j][l]:
                        nutrients[i][j]-=trees[i][j][l]
                        trees[i][j][l]+=1
                    else:
                        for o in range(l, len(trees[i][j])):
                            nutrients[i][j]+=trees[i][j][o]//2
                        trees[i][j]=trees[i][j][:l]
                        break
def fall():
    for i in range(n):
        for j in range(n):
            if trees[i][j]:
                for l in range(len(trees[i][j])):
                    if trees[i][j][l]%5==0:
                        for d in range(8):
                            ny, nx=i+dy[d], j+dx[d]
                            if 0<=ny<n and 0<=nx<n:
                                trees[ny][nx].append(1)
def winter():
    for i in range(n):
        for j in range(n):
            nutrients[i][j]+=a[i][j]
for _ in range(k):
    spring_summer()
    fall()
    winter()
answer=0
for i in range(n):
    for j in range(n):
        if trees[i][j]:
            answer+=len(trees[i][j])
print(answer)