영충이 알고리즘

16235 나무 재테크

문제에서 주어진 조건대로 구현하면 되는데 조건이 살짝 까다로울 수 있다.

평소 STL를 자주 사용해봤으면, vector나 queue와 sort를 이용하여 비교적 쉽게 풀 수 있을거라고 생각한다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, k;
int a[11][11]; //겨울에 추가되는 양분 저장
int tmp[11][11]; //현재 남아 있는 양분 저장
vector<int> map[11][11]; //(r, c)좌표에 있는 나무들의 나이 저장
int dr[] = { 0,0,1,-1,1,-1,1,-1 };
int dc[] = { 1,-1,0,0,1,1,-1,-1 };

void doSS(int r, int c) {
	int sz = map[r][c].size();
	vector<int> newTree;
	int sum = 0;

	for (int i = 0; i < sz; i++) {
		if (tmp[r][c] >= map[r][c][i]) {
			tmp[r][c] -= map[r][c][i];
			newTree.push_back(map[r][c][i] + 1);
		}
		else {
			sum += (map[r][c][i]/2);
		}
	}

	map[r][c].clear();
	for(int vv : newTree){
		map[r][c].push_back(vv);
	}

	tmp[r][c] = tmp[r][c] + sum;
}

void doF(int r, int c) {
	for (int vv : map[r][c]) {
		if (vv % 5 == 0) {
			for (int i = 0; i < 8; i++) {
				int ar = r + dr[i];
				int ac = c + dc[i];

				if (ar > 0 && ac > 0 && ar <= n && ac <= n) {
					map[ar][ac].push_back(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]);
		}
	}

	for (int i = 0; i < m; i++) {
		int x, y, age;
		scanf("%d %d %d", &x, &y, &age);

		map[x][y].push_back(age);
	}

	//초기 양분 5로 배정
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			tmp[i][j] = 5;
		}
	}

	while (k--) {
		//나이순으로 정렬하기
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				sort(map[i][j].begin(), map[i][j].end());
			}
		}

		//봄 + 여름
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				doSS(i, j);
			}
		}

		//가을
		//나무 번식
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				doF(i, j);
			}
		}

		//겨울
		//양분주기
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				tmp[i][j] += a[i][j];
			}
		}
	}

	int res = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			res += map[i][j].size();
		}
	}

	printf("%d\n", res);
}