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

[16235번 나무 재테크]
https://www.acmicpc.net/problem/16235

특별한 알고리즘없이 문제에 제시된대로 구현하는 문제였다. C++ 참조자 문법에 익숙하지 않아 메모리 에러가 계속 발생하여 꽤나 애를 먹었다. Java 주소 참조 문법과 헷갈리지 않도록 조심해야겠다.

풀이

deque를 사용하였다. deque를 사용한 이유는 한 칸의 1x1 사각형에 나무의 나이가 추가될 때(문제에 따르면 추가되는 나무의 나이는 항상 1이다) 따로 정렬을 수행할 필요가 없어지기 때문이다. 가을에 나무가 번식할 때마다 해당 사각형에 있는 나무를 정렬하면 시간 초과가 발생한다.

e.g.
r=2, c=1인 위치에 나무가 두 그루 있다고 가정한다. 나무의 나이는 1,3이다.
나이가 1인 나무는 양분을 먹고 2가 되고 3인 나무는 먹지 못하고 죽었다고 가정하면 해당 사각형의 나무는 한 그루가 남고, 그 나무의 나이는 2이다.

{1,3} -> {2}
나이가 3이었던 나무는 deque.pop_back()으로 없애준다.

여기서 가을에 주변 나무가 번식을 하여 해당 사각형에 나무 두 그루가 추가 되었다고 가정한다. 그렇게 되면 해당 사각형에 심어져 있는 나무는 총 세 그루이고, 나이는 1,1,2가 된다.

{2} -> {1,1,2}
deque.push_front(1)로 나무를 새로 심어준다.

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int ans;
int n,m,k;
int dr[] = {-1,-1,-1,0,0,1,1,1};
int dc[] = {-1,0,1,-1,1,-1,0,1};
int A[11][11];
int nutrient[11][11];
deque<int> tree[11][11];

void sol() {
	
	//spring
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			deque<int>& dq = tree[i][j];  //참조자 사용
			if(dq.size() > 0) {
				int idx = -1;
				int size = dq.size();
				for(int l=0;l<size;++l) {
					if(nutrient[i][j] >= dq[l]) {
						nutrient[i][j] -= dq[l];
						dq[l]++;
					} else {
						idx = l;
						break;
					}
				}

				//summer
				if(idx != -1) {
					for(int l=size-1;l>=idx;--l) {
						nutrient[i][j] += dq[l] / 2;
						dq.pop_back();
					}
				}
			}
		}
	}

	//autumn
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			deque<int>& dq = tree[i][j];  // 참조자 사용
			if(dq.size() > 0) {
				int size = dq.size();
				for(int l=0;l<size;++l) {
					if(dq[l] != 0 && dq[l] % 5 == 0) {
						for(int d=0;d<8;++d) {
							int ni,nj;
							ni = i+dr[d];
							nj = j+dc[d];

							if(1<=ni&&ni<=n && 1<=nj&&nj<=n) {
								tree[ni][nj].push_front(1);
							}
						}
					}
				}
			}
		}
	}

	//winter
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			nutrient[i][j] += A[i][j];
		}
	}

	return;
}

int main(void) {
	// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	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]);
			nutrient[i][j] = 5;
		}
	}

	for(int i=0;i<m;++i) {
		int r,c,age;
		scanf("%d%d%d", &r,&c,&age);
		tree[r][c].push_back(age);
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			if(tree[i][j].size() > 0) {
				sort(tree[i][j].begin(), tree[i][j].end());
			}
		}
	}

	for(int i=0;i<k;++i) {
		sol();
	}

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

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

실행 결과