반응형
16235번 나무 재테크
1. 이해하기
- 처음에 모든 칸에는 5만큼의 양분이 들어있다.
- 사계절마다 일어나는 일이 다르다.
- 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 이때 나무는 심어져있는 칸의 양분만 먹을 수 있다. 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 땅에 양분이 자신의 나이만큼 이상이 없다면 나무는 죽는다.
- 여름에는 봄에 죽은 나무가 양분으로 변한다. 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
- 가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 한다. 번식은 인접한 8개의 칸에 나이가 1인 나무로 번식된다.
- 겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다.
2. 구현하기
-
현재 살아있는 나무와 죽은 나무를 구별해서 저장한다.
- 덱을 사용하는 이유는 새로 추가된 나무를 앞에 추가하여 양분을 먹을 때 먼저 먹을 수 있도록 함이다.
-
각 계절마다 일어나는 일을 구현해준다.
void spring() { for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { int size = tree[i][j].size(); for(int k = 0; k < size; k++) { int age = tree[i][j].front(); tree[i][j].pop_front(); if(map[i][j] >= age) { map[i][j]-=age; age++; tree[i][j].push_back(age); } else { die_tree[i][j].push_back(age); } } } } } void summer() { for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { while(!die_tree[i][j].empty()) { int age = die_tree[i][j].front(); die_tree[i][j].pop_front(); map[i][j] += age/2; } } } } void autumn() { deque<int> next_tree[N][N]; for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { int size = tree[i][j].size(); for(int k = 0; k < size; k++) { int age = tree[i][j].front(); tree[i][j].pop_front(); if(age%5==0) { for(int d = 0; d < 8; d++) { int nx = i+dx[d], ny = j+dy[d]; if(nx < 0 or nx >= N or ny < 0 or ny >= N) continue; next_tree[nx][ny].push_back(1); } } tree[i][j].push_back(age); } } } for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { while(!next_tree[i][j].empty()) { int age = next_tree[i][j].front(); next_tree[i][j].pop_front(); tree[i][j].push_front(age); } } } } void winter() { for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { map[i][j] += food[i][j]; } } }
-
K년 후에 살아남은 나무의 수를 반환한다.
int simulate() { for(int i = 0; i < K; i++) { spring(); summer(); autumn(); winter(); } int ret = 0; for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { ret += tree[i][j].size(); } } return ret; }
3. 전체 코드
- 각 칸에 대해서 나무를 저장해준다. 이렇게 하지 않으면 시간 초과가 난다.
#include <iostream>
#include <deque>
using namespace std;
int map[10][10];
int food[10][10];
deque<int> tree[10][10];
deque<int> die_tree[10][10];
int dx[] = {-1,-1,-1,0,0,1,1,1};
int dy[] = {-1,0,1,1,-1,-1,0,1};
int N,M,K;
void spring() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
int size = tree[i][j].size();
for(int k = 0; k < size; k++) {
int age = tree[i][j].front(); tree[i][j].pop_front();
if(map[i][j] >= age) {
map[i][j]-=age;
age++;
tree[i][j].push_back(age);
} else {
die_tree[i][j].push_back(age);
}
}
}
}
}
void summer() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
while(!die_tree[i][j].empty()) {
int age = die_tree[i][j].front(); die_tree[i][j].pop_front();
map[i][j] += age/2;
}
}
}
}
void autumn() {
deque<int> next_tree[N][N];
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
int size = tree[i][j].size();
for(int k = 0; k < size; k++) {
int age = tree[i][j].front(); tree[i][j].pop_front();
if(age%5==0) {
for(int d = 0; d < 8; d++) {
int nx = i+dx[d], ny = j+dy[d];
if(nx < 0 or nx >= N or ny < 0 or ny >= N) continue;
next_tree[nx][ny].push_back(1);
}
}
tree[i][j].push_back(age);
}
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
while(!next_tree[i][j].empty()) {
int age = next_tree[i][j].front(); next_tree[i][j].pop_front();
tree[i][j].push_front(age);
}
}
}
}
void winter() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
map[i][j] += food[i][j];
}
}
}
int simulate() {
for(int i = 0; i < K; i++) {
spring();
summer();
autumn();
winter();
}
int ret = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
ret += tree[i][j].size();
}
}
return ret;
}
int main() {
cin >> N >> M >> K;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cin >> food[i][j];
map[i][j] = 5;
}
}
for(int i = 0; i < M; i++) {
int x,y,age;
cin >> x >> y >> age;
x--; y--;
tree[x][y].push_back(age);
}
cout << simulate() << '\n';
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 17144번 미세먼지 안녕! (0) | 2019.10.11 |
---|---|
[백준] 16236번 아기 상어 (0) | 2019.10.10 |
[백준] 16234번 인구 이동 (0) | 2019.10.09 |
[백준] 5373번 큐빙 (0) | 2019.10.08 |
[백준] 15686번 치킨 배달 (0) | 2019.10.08 |