[C++] BOJ(백준) 16235 나무 재테크

https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

 

구현 문제다. 

해당 문제는 시간제한이 짧다. 

시간제한을 신경써서 최대한 간단하게 작성하려기보단 구현을 먼저하고 시간제한을 신경쓰려고 했다.

한 칸에 여러 나무가 존재할 수 있다는 점이 생각보다 까다로웠다.

나무의 위치를 입력받는 배열로 [100][3]으로 2차원 배열 / [10][10][102]로 3차원 배열 두 가지를 생각했다.

2차원 배열은 각각의 값을 저장하는 것이고, 3차원 배열은 입력 받자마자 땅 위치에 저장하는 것이다.

입력으로 들어오는 나무는 동일한 칸에 존재하지 않기 때문에 3차원 배열을 선택했다.

(처음에는 이 조건을 못 보고 2차원 배열로 받고 정렬하겠다고 생쇼를 했다...)

 

[10][10][102]에서 102로 한 이유는 [r][c][0]에 나무의 개수, [r][c][101]에 봄에 죽은 나무의 인덱스를 저장하려 했다.

즉, [r][c][1]부터 나무의 나이가 저장되는 형태다.

작은 데이터에서는 잘 작동 했지만 큰 데이터를 넣으면 이상한 결과가 나왔다.

그 이유는 입력으로 주어지는 나무의 개수가 100개일 뿐, 가을에 번식하면 100개는 충분히 넘을 수 있었다.

(이건 계산해보진 않았지만 대충 2002로 늘리니 제대로 작동했다.)

 

< 봄 >

전체 탐색 중 나무가 있는 칸에 대해서만 양분을 줬다.

양분은 나이가 어린 나무부터 먹을 수 있기 때문에 양분을 주기 전 정렬을 했다.

정렬은 해당 칸의 [r][c][1] (처음) 부터 [r][c][[r][c][0]] (나무의 개수) 까지 했다.

그 후 양분이 나무의 나이보다 많다면 양분을 섭취했다.

정렬이 되어 있기 때문에 양분이 적어지는 순간이 오면 반복문을 멈췄다.

 

< 여름 >

봄과 동일하게 전체 탐색 중 나무가 있는 칸에 대해서만 죽은 나무를 양분으로 바꿨다.

다시 처음부터 양분과 나무의 나이를 비교하면 봄에 나이를 먹은 나무가 죽을 수도 있기 때문에

봄에 죽은 나무의 인덱스를 따로 저장했다. ( [r][c][2001] )

이 때, [r][c][0]의 나무 개수를 한 개 줄여줬다.

 

< 가을 >

봄과 동일하게 전체 탐색 중 나무가 있는 칸에 대해서만 번식을 했다.

해당 칸의 모든 나무들을 탐색하여 나이가 5의 배수인 나무들은 8방향으로 번식했다.

이 때, 나무의 개수를 하나 늘리고 [r][c][0]번째 나무를 나이 1로 추가했다.

 

< 겨울 >

현재 양분에 처음에 입력받은 매년 증가하는 양분의 수를 증가시킨다.

 

[r][c][0]들에 나무의 개수가 저장되어 있으므로 합을 구해 출력했다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int k, n, m;
int tree[10][10][2002];	// 나무
/*tree의 첫번째 칸은 나무의 개수를 저장하는데 사용
tree의 마지막 칸은 봄에 죽은 나무의 인덱스를 저장하는데 사용*/
int arr[10][10];	// 매년 증가하는 양분 수
int bab[10][10];	// 현재 양분 수

// 가을에 번식을 위함
int dr[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			bab[i][j] = 5;
		}

	for (int i = 0; i < m; i++) {
		int r, c, a;	cin >> r >> c >> a;
		tree[r - 1][c - 1][0] = 1;
		tree[r - 1][c - 1][1] = a;
	}

	for (int i = 0; i < k; i++) {
		// 봄
		for (int r = 0; r < n; r++)
			for (int c = 0; c < n; c++)
				if (tree[r][c][0]) {
					// 나이 어린 순으로 양분을 섭취하기 때문에 정렬
					if (tree[r][c][0] > 1)	sort(tree[r][c] + 1, tree[r][c] + tree[r][c][0] + 1);
					tree[r][c][2001] = 1;	// 죽은 나무의 위치를 파악하기 위함

					// 해당 칸에 있는 모든 나무를 검사
					for (int j = 1; j <= tree[r][c][0]; j++) {
						if (bab[r][c] >= tree[r][c][j]) {
							bab[r][c] -= tree[r][c][j];
							tree[r][c][j]++;
							tree[r][c][2001] = j + 1;
						}
						else break;
					}
				}

		// 여름
		for (int r = 0; r < n; r++)
			for (int c = 0; c < n; c++)
				if (tree[r][c][0]) {
					int cnt = tree[r][c][0];

					// 해당 칸의 죽은 나무들 처리
					for (int j = tree[r][c][2001]; j <= cnt; j++) {
						bab[r][c] += tree[r][c][j] / 2;
						tree[r][c][0]--;
					}
				}

		// 가을
		for (int r = 0; r < n; r++)
			for (int c = 0; c < n; c++)
				if (tree[r][c][0]) {

					// 해당 칸의 모든 나무들 탐색
					for (int j = 1; j <= tree[r][c][0]; j++) {
						if (tree[r][c][j] % 5 == 0) {

							// 8방향 탐색
							for (int l = 0; l < 8; l++) {
								int rr = r + dr[l];
								int cc = c + dc[l];

								// 범위를 벗어 나면 continue
								if (rr < 0 || rr >= n || cc < 0 || cc >= n) continue;

								tree[rr][cc][0]++;
								tree[rr][cc][tree[rr][cc][0]] = 1;
							}
						}
					}
				}

		// 겨울
		for (int r = 0; r < n; r++)
			for (int c = 0; c < n; c++)
				bab[r][c] += arr[r][c];
	}

	// tree의 [r][c][0]의 합으로 나무의 개수를 구할 수 있음
	int re = 0;
	for (int r = 0; r < n; r++)
		for (int c = 0; c < n; c++)
			re += tree[r][c][0];

	cout << re;
}

 

별 생각 없이 0부터 시작하는 배열로 코드를 짜고 문제는 1부터 시작하는 배열이었다는 걸 알아서

입력받고 r-1, c-1로 배열에 저장했다.