[BOJ][16235] 나무 재테크

문제 : www.acmicpc.net/problem/16235

---

N x N 크기의 땅. 처음 모든 땅에는 5만큼의 양분이 들어있다. 한 칸의 땅에는 여러 개의 나무가 심어질 수 있다.

M 개의 나무를 심었다. (x, y, z) = (x 좌표, y 좌표, 나이)

K 년 후 살아있는 나무 개수를 구하라.

 

봄 : 나무가 자신 나이만큼의 양분을 먹으면 나이가 1 증가. 양분 못 먹으면 죽는다. 자신의 칸의 양분만 먹을 수 있다. 나이가 작은 순 부터 양분 섭취.

여름 : 죽은 나무가 양분(나이/2)으로 변한다.

가을 : 나무의 나이가 5의 배수일 때 인접한 8 칸에 나이가 1인 나무가 생긴다.

겨울 : A 배열만큼의 양분이 추가된다.

---

구현 문제.

배열은 총 3개를 사용했다.

lands : 각 칸에 있는 나무의 나이. 3차원 배열. lands[x][y][k] = (x,y) 칸에 있는 k번째로 나이많은 나무의 나이를 의미한다. 즉, lands[x][y]는 나이순으로 내림차순 정렬된다. 입력시 각 칸을 내림차순 정렬해준다.

feed : 각 칸에 있는 양분. 2차원 배열

A : 매년 추가되는 양분을 저장하는 2차원 배열

 

봄

lands[x][y] 배열은 나이 기준으로 내림차순 정렬되어 있다. 이유는 가을에 나이가 1인 나무가 생길 수 있는데 이 때 lands[x][y] 배열의 뒤에 추가하고 싶기 때문이다. 생성되는 나무를 뒤에 넣어주면 항상 내림차순이 유지된다.

나이가 작은 순부터 양분을 섭취하기 때문에 lands[x][y] 배열을 뒤에서 부터 탐색하면서 feed[x][y]의 남은 양분과 탐색중인 나무의 나이를 비교해서 양분이 나무의 나이보다 작은 경우 탐색을 종료한다. 양분이 나무 나이보다 같거나 크다면 feed[x][y]는 나무의 나이만큼 감소하고 나무 나이는 1 증가한다.

탐색이 종료된 시점의 인덱스를 k라 한다면 k + 1개의 나무가 양분을 얻지못했다는 뜻이다. 즉, 앞에서부터 k+1개의 나무는 lands[x][y] 배열에서 삭제한다. 삭제하기 전에 죽은 나무들의 나이 / 2 는 여름에 양분으로 변경되기 때문에 삭제되는 나무 나이/2 합을 저장해둔다.

 

여름

봄에 삭제된 나무 나이/2 합을 feed[x][y]에 추가한다.

 

가을

lands[x][y]의 모든 나무 나이를 탐색하면서 탐색중인 나무 나이가 5 배수라면 (x, y)를 기준으로 인접한 8칸을 방문하면서 1인 나무를 추가해준다.

 

겨울

feed[i][j]에 A[i][j]를 더한다.

 

위 로직을 K 번 반복한다.

모든 땅의 칸(lands)에 있는 살아남은 나무의 개수가 정답이 된다.

 

시간복잡도는 대충보면 O(N^2 + K) 플러스 α(가을에 나무가 추가 되므로)

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/BOJ/16235.%20%EB%82%98%EB%AC%B4%20%EC%9E%AC%ED%85%8C%ED%81%AC.cpp