백준 16235 - 나무 재테크

문제 링크입니다 https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

 

삼성 SW 역량 테스트 기출문제입니다.

만들어야할 배열의 크기는 작지만, 시간이 0.3초(c++기준)로 매우 짧습니다. 따라서 효율적이고 간결하게 만들어야 시간 초과를 피할 수 있습니다.

문제에서는 나무 재테크를 하려고 합니다. 봄, 여름, 가을, 겨울 각각의 계절마다 해야할 일이 전부 다릅니다.

 

1. 봄의 경우

나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가합니다. 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무  부터 양분을 먹습니다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.

 

2. 여름의 경우

봄에 죽은 나무가 양분으로 변하게 됩니다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버립니다.

 

3. 가을의 경우

나무가 번식합니다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생깁니다. 어떤 칸 (r, c)와 인접한 칸은 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1) 입니다. 

 

4. 겨울의 경우

땅을 돌아다니면서 땅에 양분을 추가합니다. 각 칸에 추가되는 양분의 양은 A[r][c]입니다.

 

조건을 보면 봄과 여름은 비슷한 일을 함으로 한번에 합쳐서 함수를 만들었습니다. 가을, 겨울은 모두 따로 만들었습니다. 처음 문제를 본다면 코드를 구성하는 것이 막막할 수 있지만 하나씩 조건을 맞춰나가면서 풀면 그다지 어려운 문제는 아닙니다.(시간초과에 주의해주세요)

 

각각의 칸에 자라고 있는 나무는 백터에 저장해주면서 풀었습니다.

이 문제는 코드를 보면 완전히 이해하실 겁니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int N, M, K; //N*N = SiZE;
int nutrient[11][11];
int plus_[11][11];
vector<int> have[11][11];
int arr[8] = { 1,0,-1,0,1,-1,1,-1};
int arr2[8] = { 0,1,0,-1,1,-1,-1,1 };
int number_tree;

void spring_summer() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (have[i][j].size() == 0) continue;
			int cnt_get = 0;
			vector<int> tree;
			sort(have[i][j].begin(), have[i][j].end());
			for (int z = 0; z < have[i][j].size(); z++) {
				if (nutrient[i][j] >= have[i][j][z] && have[i][j][z] > 0) {
					nutrient[i][j] -= have[i][j][z];
					tree.push_back(have[i][j][z] + 1);
				}
				else {
					cnt_get += have[i][j][z] / 2;
					have[i][j][z] = 0;
				}
			}
			have[i][j].clear();
			for (int z = 0; z < tree.size(); z++) {
				have[i][j].push_back(tree[z]);
			}
			nutrient[i][j] += cnt_get;
		}
	}
}

void fall() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (have[i][j].size() > 0) {
				for (int z = 0; z < have[i][j].size(); z++) {
					if (have[i][j][z] % 5 == 0 && have[i][j][z] > 0) {
						for (int a = 0; a < 8; a++) {
							if (i + arr[a] > 0 && i + arr[a] <= N && j + arr2[a] > 0 && j + arr2[a] <= N) {
								have[i + arr[a]][j + arr2[a]].push_back(1);
							}
						}
					}
				}
			}
		}
	}
}

void winter() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			nutrient[i][j] += plus_[i][j];
		}
	}
}

void solve() {
	spring_summer();
	fall();
	winter();
}

int main() {
	cin.tie(0);
	cout.tie(0);
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &plus_[i][j]);
			nutrient[i][j] = 5;
		}
	}
	for (int i = 0; i < M; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		have[a][b].push_back(c);
	}
	for (int k = 0; k < K; k++) {
		solve();
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			number_tree += have[i][j].size();
		}
	}
	cout << number_tree;
	return 0;
}

 

질문 및 조언 댓글 남겨주세요!