나무 재테크
문제 해석
주어진 양분과 나무의 정보로 나무 재테크를 K년 하고, 땅에 살아있는 나무의 개수를 구하는 문제입니다.
NxN땅에 초기에 5의 양분이 있습니다.
나무 재테크는 다음의 과정을 K번 거칩니다.
- 봄
- 나무가 자신의 나이만큼 양분을 먹고 나이가 1 증가합니다.
- 하나의 칸에 여러개의 나무가 있으면, 나이 어린 나무부터 양분을 먹습니다.
- 만약 나이만큼 양분을 먹지 못하면 죽습니다.
- 여름
- 죽은 나무가 양분으로 변합니다.
- 각 나무의 나이/2씩 양분이 추가됩니다.(소수점 버림)
- 가을
- 나이가 5배수인 나무가 번식합니다.
- 인접한 8칸에 나이 1인 나무가 생성됩니다.
- 겨울
- 양분을 추가합니다.
설계(15)
실행시간이 0.3초이내로, 아주 짧은 실행시간을 요구하는 구현문제입니다.
먼저 봄,여름 & 가을,겨울 두 부류로 나누어서 구현합니다.
- 봄,여름
- 나무의 정보를 2차원 배열에 담되 deque 자료구조를 사용합니다. 이유는 가을에 새로운 나무가 생성되는데 이 나무들을 앞에 배치하기 위함입니다.
- 남아있는 나무들은 나이가 1보다 큰 것을 보장하기 때문에 가능한 방법입니다.
- 나무가 있는 곳의 좌표를 탐색해서 양분이 부족한 나무를 찾기까지 반복합니다.
- 양분이 되는 나무는 각 나이를 1씩 증가시킵니다.
- 양분이 안되는 나무를 찾으면, 해당 나무를 포함한 남은 나무들을 모두 양분으로 추가하도록 처리합니다.
- 가을,겨울
- 나이가 5의 배수인 나무를 찾고 나이 1인 나무를 각 좌표의 앞에 추가합니다.
- 이와 동시에 양분을 추가합니다.
구현(15)
코드
#include <iostream>
#include <deque>
using namespace std;
#define MAXN 10
int nut[MAXN][MAXN];
int arr[MAXN][MAXN];
int N,M,K;
deque<int> tree[MAXN][MAXN];
int dx[] = {-1,-1,-1,0,0,1,1,1};
int dy[] = {-1,0,1,-1,1,-1,0,1};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M>>K;
for (int i = 0 ; i<N;i++){
for (int j=0;j<N;j++){
cin >> nut[i][j];
arr[i][j] = 5;
}
}
while (M--){
int x,y,cnt;
cin >> x >> y >> cnt;
x--;
y--;
tree[x][y].push_back(cnt);
}
while (K--){
// 봄,여름
for (int i = 0 ;i <N; i++){
for (int j=0;j<N;j++){
if (!tree[i][j].size()) continue;
for (int k = 0 ;k< tree[i][j].size(); k++){
int cur = tree[i][j][k];
if (arr[i][j] - cur < 0){
int cnt = tree[i][j].size() - k;
while (cnt--){
arr[i][j] += tree[i][j].back()/2;
tree[i][j].pop_back();
}
break;
}
else{
arr[i][j] -= cur;
tree[i][j][k]++;
}
}
}
}
// 가을, 겨울
for (int i = 0 ; i<N; i++){
for (int j=0;j<N;j++){
for (int k = 0; k<tree[i][j].size(); k++){
int cur = tree[i][j][k];
if (tree[i][j][k]%5==0){
for (int kk = 0 ; kk < 8; kk++){
int nx = i + dx[kk];
int ny = j + dy[kk];
if (nx < 0 || ny < 0 || nx>=N || ny>=N) continue;
tree[nx][ny].push_front(1);
}
}
}
arr[i][j] += nut[i][j];
}
}
}
int ans = 0;
for (int i = 0; i < N ;i++){
for (int j= 0;j<N;j++){
ans += tree[i][j].size();
}
}
cout << ans <<"\n";
return 0;
}
디버깅
제출결과
100 ms
마무리
최적화가 필요한 구현문제였습니다. 나무의 나이와 개수를 이용하여 최적화하는 방법이 있긴 하지만 시간안에 나왔으므로 굳이 추가 구현하지 않았습니다.