[백준 16235번 - 나무 재테크] C++ 풀이

16235번.

 

자료구조는 2차원 배열 안에 deque 를 넣는 것으로 n * n 땅을 표현했다.

구현은 빠르게 했지만 계속 43% 정도에서 시간초과가 떠서 잡느라 매우 오랜 시간을 소요했다ㅜ.......

 

시간을 줄이는데 도움이 되었던 것은

1. 구조체 없애기

처음에는 tree 구조체를 써서 했지만 2차원 배열에 저장하므로서 위치를 따로 갖고있을 필요가 없어져서 그냥 나무 나이만 deque 에 저장하는 것으로 했더니 47%에서 시간초과가 났다.

2. deque 자료구조로 sort 함수를 없애기

가을에 새로 생기는 나무들을 deque 의 front 에 push 해줌으로서 정렬할 필요가 없어졌다. 새로 생기는 나무는 나이가 1로 기존의 나무보다는 작을 것이기 때문이다. 그래서 봄에 나이 적은 순서대로 나이 추가해줄때 정렬할 필요가 없다. 이렇게 했더니 정답이 뜸.

 

다음과 같은 케이스라고 가정해보자.

1 1 1000

100

1 1 1

 

양분은 최대인 100이 매년 주어지고, 나무의 나이는 1살부터 시작한다.

100년이 지나면

(1, 1)칸의 양분 누적량은 100 * 100 = 10000 ( 1만 )

양분 사용량은 1 + 2 + .. + 100 = 100 * 99 / 2 = 4995 ( 약 5천 )

따라서 나무는 100살 이상 살 수 있다.

1000년이 지났을 때 양분 누적양 10만 사용량 50만이다. 모든 나무가 1000년을 모두 살지는 못한다.

 

각 칸의 있는 나무 수를 대략적으로 계산해보면 ( 인접한 칸이 모두 8개라고 가정하였을 때 )

5년 : 1살 * 8 + 5살 * 1 = 8 * 1 + 1

10년 : 1살 * 8 + 5살 * 8 + 10살 * 1 = 8 * 2 + 1

15년 : 1살 * 8 + 5살 * 8 + 10살 * 8 + 15살 * 1 = 8 * 3 + 1

...

100년 : 8 * 20 + 1 = 161그루

... 

1000년 : 8 * 200 + 1 = 1601그루

 

다음과 같다고 가정했을 때

n = 10,

나무 = 100그루, 각 나무의 나이는 1살

k = 1000

 

내 알고리즘의 시간 복잡도는 

( n^2 * 각 칸의 나무 개수 + n^2 * 각 칸의 나무 중 나이가 5의 배수인 나무의 개수 * 8 ) * k + n^2 

과 같다. 빅오 표기법으로 하면 O(n^2 + n^2 * k + k ^ 2) 가 되겠다.

 

k = 10 일때

( 10 * 10 * 16 + 2 * 10 * 10 * 10 * 8 ) * 10 + 10 * 10 = ( 1600 + 16000 ) * 10 + 100 = 176100

k = 1000 일때

176100 * 100 = 17610000

문제의 시간제한이 0.3초 이므로 30000000번 안쪽의 연산이 가능해 통과할 수 있었다.

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <deque>

using namespace std;

int n, m, k;

int a[11][11];
int nutri[11][11];
deque<int> trees[11][11];

int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

int main() {
	scanf("%d %d %d", &n, &m, &k);

	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			scanf("%d", &a[i][j]);
			nutri[i][j] = 5;
		}
	}

	for(int i = 0; i < m; ++i) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		trees[x][y].push_back(z);
	}

	for(int t = 0; t < k; ++t) {
		// 봄
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= n; ++j) {
				int size = trees[i][j].size();
				// 양분 먹고 나이 +1
				int k =  0;
				for(; k < trees[i][j].size(); ++k) {
					if (nutri[i][j] >= trees[i][j][k]) {
						nutri[i][j] -= trees[i][j][k];
						trees[i][j][k]++;
					} else {
						break;
					}
				}
				// 여름
				// 죽은 나무 있는 곳 양분 추가
				for(int p = trees[i][j].size() - 1; p >= k; --p) {
					nutri[i][j] += trees[i][j][p] / 2;
					trees[i][j].pop_back();
				}
			}
		}

		// 가을
		// 나무 번식
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= n; ++j) {
				if (trees[i][j].size() > 0) {
					for(int k = 0; k < trees[i][j].size(); ++k) {
						if (trees[i][j][k] % 5 == 0) {
							for(int q = 0; q < 8; ++q) {
								int nx = i + dx[q];
								int ny = j + dy[q];
								if (nx < 1 || nx > n || ny < 1 || ny > n)
									continue;
								else {
									trees[nx][ny].push_front(1); // 새로 추가되는 나무를 앞쪽에 넣으면 정렬할 필요 X
								}
							}
						}
					}
				}
				// 겨울
				// 양분 추가
				nutri[i][j] += a[i][j];
			}
		}
	}

    int tree_cnt = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			if (trees[i][j].size() > 0) {
				tree_cnt += trees[i][j].size();
			}
		}
	}

	printf("%d\n", tree_cnt);
	return 0;
}