Algorithm/백준
[BOJ] - 16235. 나무 재테크
benguin
2019. 4. 8. 19:10
[URL]
https://www.acmicpc.net/problem/16235
16235번: 나무 재테크
부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든
www.acmicpc.net
[문제 풀이]
* 시뮬레이션
1. vector , queue 로 구현
2. STL - sort를 사용하여 비교적 쉽게 정렬한 후 K년 후 최종적으로 나오는 나무 개수 계산
-----------------------------------------------------------------------------------------------------------
첫 번째 시도 - 시간 초과
원인: 여름에 나무 죽이기 for문 제어 실패
[소스 코드]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, K;
int A[11][11]; // 매년 추가되는 양분의 수
int map[11][11]; // 양분
struct TREE {
int x;
int y;
int age;
};
vector <TREE> v;
int dx[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int dy[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int cnt = 0;
void init();
bool cmp(const TREE &a, const TREE &b);
int main()
{
init();
for (int k = 0; k < K; k++)
{
sort(v.begin(), v.end(), cmp);
/////////////////////
vector<TREE> alive;
vector<TREE> dead;
vector<TREE> five;
vector<TREE> birth;
/////////////////////
// 봄
for (int i = 0; i < v.size(); i++)
{
TREE temp;
temp = v[i];
if (map[temp.x][temp.y] >= temp.age)
{
// 양분 충분 - > 나무 나이 + 1
map[temp.x][temp.y] = map[temp.x][temp.y] - temp.age;
temp.age++;
alive.push_back(temp);
if (temp.age % 5 == 0)
five.push_back(temp);
}
else
{
// 양분 부족 - > 나무 죽음
dead.push_back(temp);
}
}
// 여름
for (int i = 0; i < dead.size(); i++)
{
TREE temp;
temp = dead[i];
int death = temp.age / 2;
map[temp.x][temp.y] += death;
}
// 가을
for (int i = 0; i < five.size(); i++)
{
int x = five[i].x;
int y = five[i].y;
for (int j = 0; j < 8; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) {
birth.push_back({ nx, ny, 1 });
}
}
}
// 겨울
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
map[i][j] += A[i][j];
}
}
v.clear();
for (int i = 0; i < alive.size(); i++)
{
TREE temp;
temp = alive[i];
v.push_back(temp);
}
for (int i = 0; i < birth.size(); i++)
{
TREE temp;
temp = birth[i];
v.push_back(temp);
}
alive.clear();
birth.clear();
dead.clear();
five.clear();
cnt = v.size();
}
printf("%d\n", cnt);
return 0;
}
void init() {
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]);
map[i][j] = 5;
}
}
for (int i = 0; i < M; i++)
{
int x, y, age;
scanf("%d %d %d", &x, &y, &age);
v.push_back({ x, y, age });
}
}
bool cmp(const TREE &a, const TREE &b) {
if (a.x == b.x && a.y == b.y)
return a.age < b.age;
else {
if (a.x == b.x)
return a.y < b.y;
else
return a.x < b.x;
}
}
|
cs |