문제 정보
백준 ( BOJ ) 16235 나무 재테크
문제 풀이 : 시뮬레이션
문제 출처 : https://www.acmicpc.net/problem/16235
시작 Thinking
어떤 데이터 구조를 사용 할 것인가?
이 문제의 최대 난제입니다.
제한을 다시 한 번 짚고 넘어 가 봅시다.
1 ≤ N ≤ 10 - 칸의 갯수
1 ≤ M ≤ N2 - 처음 나무 갯수
1 ≤ K ≤ 1,000 - 년
1 ≤ A[r][c] ≤ 100 - 매년 겨울 영양 공급량
1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10
아직 감이 잘 안올 수도 있습니다.
나무의 나이는 몇살 까지 자랄 수 있을까요?
이분은 천년까지 제테크 하실 수 있습니다..
극단적으로 생각 해 봅시다.
1 1 1000
100
1 1 1
이 경우가 나무가 가장 오랫동안 자랄 수 있는 데이터 겠죠?
나무는 한살부터 자라기 시작합니다.
100년이 지나면, 100* 100 + 5 만큼의 양분이 누적 되었을 것이고,
사용량은 1+2+3 + … + 100 까지 자랐겠죠?
즉 100*99/2 만큼 양분을 쓴겁니다.
아직 한참이네요.
그럼 천년이 지나면, 양분은 총 100* 1000 = 100000만큼 쌓이네요.
그럼 누적 소비량은, 1000*999 / 2 입니다.
양분이 남습니다.
그러니 그냥 나무는 1010살까지 자랄 수 있는걸로 생각하고 풀면 됩니다.
그럼 나무를, 나이를 기준으로 분류 하고 0 ~ 1010 까지 탐색을 하고,
1000년을 본다면?
1010* 1000 탐색이죠. 총 1010000 입니다.
이정도면 시간이 그렇게 크게 걸리지 않습니다.
왜냐하면, 탐색하지 않고 넘어가는 비율이 훨씬 클거 거든요.
0부터 시작해서,
봄에는
[i] 에 있던 나무를, [i+1] 로 옮겨주면 됩니다.
그리고, 시간 절약을 위해서, 삽입,삭제에 시간 복잡도가 O(1)인 큐를 사용 하기로 했습니다.
그렇다면, 나무는 이렇게 되겠네요.
vector<queue<pair<int,int»
복잡해 보이지만 간단합니다.
예를들어 3칸짜리 라고 한다면;
백터 / 큐
[0] - a - b -c
[1] - d
[2] - e
이런식으로 들어간다고 생각하시면 됩니다.
백터 위치를 알려주고, 그대로 pop, push 해주면 되는거에요.
다만 인자가 pair니까,
들어갈떈, make_pair(),
값 꺼낼떈, front().first
이런식으로 꺼내 주어야 겠지요.
봄 제외하면, 나머지는 구현하기 어렵지 않으니, 코드를 먼져 보시고,
봄에 대해 좀더 설명을 드리겠습니다.
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, k;
vector<vector<int>> square;
vector<vector<int>> give;
vector<queue<pair<int,int>>> trees (1020);
class forSummer{
public :
int r, c, count;
forSummer(int q, int w, int e) {
r = q;
c = w;
count = e;
}
};
queue<forSummer> giver;
void spring() {
int r, c;
int size, befSize;
befSize = trees[0].size();
for (int i = 0; i < 1019;i++) {
size = trees[i + 1].size();
for(int j =0 ; j < befSize; j++){
r = trees[i].front().first;
c = trees[i].front().second;
trees[i].pop();
if (square[r][c] < i) {
giver.push(forSummer(r, c, i / 2));
}
else {
square[r][c] -= i;
trees[i + 1].push(make_pair(r, c));
}
}
befSize = size;
}
}
void summer() {
while (!giver.empty()) {
square[giver.front().r][giver.front().c] += giver.front().count;
giver.pop();
}
}
void grow(int r, int c) {
r--;
if (r >= 0 && c >= 0 && r < n && c < n)
trees[1].push(make_pair(r, c));
c++;
if (r >= 0 && c >= 0 && r <n && c < n)
trees[1].push(make_pair(r, c));
c -= 2;
if (r >= 0 && c >= 0 && r < n && c < n)
trees[1].push(make_pair(r, c));
r++;
if (r >= 0 && c >= 0 && r < n && c < n)
trees[1].push(make_pair(r, c));
c+=2;
if (r >= 0 && c >= 0 && r < n && c < n)
trees[1].push(make_pair(r, c));
r++;
if (r >= 0 && c >= 0 && r < n && c < n)
trees[1].push(make_pair(r, c));
c--;
if (r >= 0 && c >= 0 && r < n && c < n)
trees[1].push(make_pair(r, c));
c--;
if (r >= 0 && c >= 0 && r < n && c < n)
trees[1].push(make_pair(r, c));
}
void fall() {
queue<pair<int, int>> backUp;
int r, c;
for (int i = 5; i < 1020; i += 5) {
while (!trees[i].empty()) {
r = trees[i].front().first;
c = trees[i].front().second;
trees[i].pop();
backUp.push(make_pair(r, c));
grow(r, c);
}
while (!backUp.empty()) {
r = backUp.front().first;
c = backUp.front().second;
backUp.pop();
trees[i].push(make_pair(r, c));
}
}
}
void winter() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
square[i][j] += give[i][j];
}
}
}
int result() {
int r = 0;
for (int i = 0; i < 1020; i++) {
r += trees[i].size();
}
return r;
}
int main() {
int r, c, y;
cin >> n >> m >> k;
square.assign(n, vector<int>(n, 5));
give.assign(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> give[i][j];
}
}
for (int i = 0; i < m; i++) {
cin >> r >> c >> y;
trees[y].push(make_pair(r-1, c-1));
}
for (int i = 0; i < k; i++) {
spring();
summer();
fall();
winter();
}
cout << result();
return 0;
}
봄
void spring() {
int r, c;
int size, befSize;
befSize = trees[0].size();
for (int i = 0; i < 1019;i++) {
size = trees[i + 1].size();
for(int j =0 ; j < befSize; j++){
r = trees[i].front().first;
c = trees[i].front().second;
trees[i].pop();
if (square[r][c] < i) {
giver.push(forSummer(r, c, i / 2));
}
else {
square[r][c] -= i;
trees[i + 1].push(make_pair(r, c));
}
}
befSize = size;
}
}
0~ 1019살 까지 나무들을 모두 들여다 봅니다.
물론, 0 이 아니라, 1부터 봐도 되는데 저의 실수…
우선, size와 befSize 를 쓰는 이유는요,
앞에 나무에서 한살 먹어서 뒤로 그대로 넘겨주면,
아래서부터 나이를 먹어야 하기 때문에, 한번 자란 나무가 또 자라는 불상사가 생깁니다.
그래서, 미리 다음 큐의 사이즈를 알아 두고,
그 다음 진행 할 때, 알아 놓은 큐 사이즈 만큼만
큐에서 뺴주시면 됩니다.
그러면 새로 들어 온 애들은 잘 남아 있곘죠.
후기
시간 : 1시간 6분
난이도 : 조금 생각 해야 할 것이 많은 문제.. 어떻게 구현 할 것인가,
어떤 데이터 구조를 쓸 것인가. 정말 고민이 많이 되던…
그리고 끝나고 나서 다른 분들 코드를 살짝 염탐 해 봤다.
역시, 아이디어 좋으신 분들이 많다…
나이 어린 나무가 새로 생길때 마다, 백터 맨 뒤에 push_back 으로 넣어주고,
역순으로 탐색 하시던.;