문제 주소 : www.acmicpc.net/problem/16235
16235번: 나무 재테크
부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터
www.acmicpc.net
c언어 스타일로 벡터 등 컨테이너 없이 풀면 메모리는 적게 나오지만 가끔 0ms가 나오지만 보통 4ms가 나옵니다.
빈 배열과 나무 나이 등 조건이 더 많아지기 때문에 처리해야 할 조건문이 많아지기 때문인 것 같습니다.
문제 확인
따로 특별한 알고리즘이 필요하지 않습니다. 제한시간과 메모리 초과가 관건입니다.
문제 조건
- 봄 : 나이가 낮은 순 부터 나무가 땅의 양분을 먹고 나이가 1 증가, 양분이 부족하면 남은 나무들은 즉시 죽습니다.
- 여름 : 봄에 죽은 나무들의 나이의 절반만큼 양분으로 돌아갑니다.
- 가을 : 나이가 5배수인 나무 주변 8방향에 나이가 1인 나무가 생성됩니다.
- 모든칸에 입력받은 양분이 추가됩니다.
처음엔 우선순위 큐를 활용하여 나무의 나이 기준으로 정렬하고 탐색을 하였습니다. 하지만 가을에 8방향으로 퍼저 나가기 때문에 나무의 수가 많이 늘어나서 시간초과, 메모리 초과가 났습니다.
deque를 사용하는 경우 벡터를 사용한 풀이에 비하여 속도차이가 많이 납니다.
따라서 배열 혹은 벡터, list를 사용하는 것이 좋습니다.
풀이
문제를 자세히 보면 양분 값을 참조하고 변경하게 되는 계절은 봄, 여름, 겨울 입니다. 또한 봄, 여름, 겨울 과정에 의해 인접 칸이 영향받지 않으므로 가을을 제외하고 나머지 3계절의 과정을 합칠 수 있습니다.
* 이때 조심해야 할 것은 봄의 과정이 끝난 후 여름과 겨울 과정을 진행해야 오류가 생기지 않습니다.
가을 과정은 인접칸에 영향을 미치므로 따로 처리를 해야 합니다.
코드
속도최적화(C++)
|
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
|
#include <cstdio>
#include <vector>
using namespace std;
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 },
dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
vector<pair<int, int>> tree[10][10];//나이 개수
int ary[10][10], s2d2[10][10];
int N, M, K;
void spring_summer_winter() {
//spring
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
int total_add = s2d2[i][j];
for (int t = tree[i][j].size() - 1; t >= 0; t--) {
int level = tree[i][j][t].first;
if (level * tree[i][j][t].second <= ary[i][j]) {//그 나이대 나무를 모두 살릴 수 있는 경우
ary[i][j] -= level * tree[i][j][t].second;
tree[i][j][t].first++;
}
else {//일부 혹은 전부 죽는 경우
int e = t + 1;
int alive = ary[i][j] / level, dead = tree[i][j][t].second - alive;
if (alive) {
ary[i][j] -= alive * level;
tree[i][j][t].first++;
tree[i][j][t].second = alive;
e--;//아직 살아있는 나무가 있기 때문에 삭제할 벡터 위치를 당김
}
//summer
total_add += dead * (level >> 1); //죽은 나무 양분으로 변경
for (t--; t >= 0; t--)//뒤에 나이가 더 많은 나무들을 모두 죽임
total_add += (tree[i][j][t].first >> 1) * tree[i][j][t].second;
tree[i][j].erase(tree[i][j].begin(), tree[i][j].begin() + e);//지정된 위치까지 나무들 정보 삭제
}
}
ary[i][j] += total_add; //winter
}
}
void winter() {
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (auto &t : tree[i][j])
if (t.first % 5 == 0)
for (int d = 0; d < 8; d++) {
int nx = dx[d] + i, ny = dy[d] + j;
if (0 <= nx && nx < N && 0 <= ny && ny < N) {
if (tree[nx][ny].size() && tree[nx][ny].back().first == 1)
tree[nx][ny].back().second += t.second;
else
tree[nx][ny].emplace_back(1, t.second);
}
}
}
void solve() {
int cnt = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (auto t : tree[i][j])
cnt += t.second;
printf("%d", cnt);
}
int main() {
scanf("%d%d%d", &N, &M, &K);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
ary[i][j] = 5;
scanf("%d", &s2d2[i][j]);
}
int x, y, z;
for (int i = 0; i < M; i++) {
scanf("%d%d%d", &x, &y, &z);
tree[--x][--y].emplace_back( z, 1 );
}
while (K--) {
spring_summer_winter();
winter();
}
solve();
}
|
cs |
메모리 최적화(C)
|
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
|
#include <stdio.h>
typedef struct tile {
short level[2], max_level;
short resource, s2d2;
}tile;
tile tree[10][10];
short N;
char dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 },
dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
void spring_summer_winter() {
//spring
for (char i = 0; i < N; i++)
for (char j = 0; j < N; j++) {
short total_add = tree[i][j].s2d2;
if (tree[i][j].max_level) {
char new_max = 0;
for (char t = 1; t <= tree[i][j].max_level; t++) {
if (tree[i][j].level[t]) {
if (t * tree[i][j].level[t] <= tree[i][j].resource) {//나이대 모든 나무를 살릴 수 있는 경우
tree[i][j].resource -= t * tree[i][j].level[t];
new_max = t;//최대 나이대를 계속해서 갱신 해야함
}
else {//일부 혹은 모든 나무가 죽는 경우
short alive = tree[i][j].resource / t, dead = tree[i][j].level[t] - alive;
if (alive) {
tree[i][j].level[t] = alive;
tree[i][j].resource -= alive * t;
new_max = t;//나무가 일부 살아있으면 최대나이로 설정, 모두 죽는 경우면 그전 단계(or 0)으로 설정
}
//summer
total_add += dead * (t >> 1);
for (t++; t <= tree[i][j].max_level; t++)
if (tree[i][j].level[t])
total_add += (t >> 1) * tree[i][j].level[t];//죽은 나무들 양분으로 변경
break;
}
}
}
tree[i][j].max_level = new_max;//최대 나무 나이 갱신
if (new_max)
for (short t = tree[i][j].max_level++; t >= 1; t--)
tree[i][j].level[t + 1] = tree[i][j].level[t]; //살아 있는 나무들 나이 증가
tree[i][j].level[1] = 0;
}
tree[i][j].resource += total_add; //winter
}
//autumn
for (char i = 0; i < N; i++)
for (char j = 0; j < N; j++) {
short total_count = 0;
for (short t = 5; t <= tree[i][j].max_level; t += 5) {
if (tree[i][j].level[t])
total_count += tree[i][j].level[t];//번식할 나무 개수 구하기
}
if (total_count) {
for (char d = 0; d < 8; d++) {
short nx = dx[d] + i, ny = dy[d] + j;
if (0 <= nx && nx < N && 0 <= ny && ny < N) {
tree[nx][ny].level[1] += total_count;//개수 만금 8방향으로 전파
if (!tree[nx][ny].max_level)
tree[nx][ny].max_level = 1;//나무가 없는 조건을 max_count로 하였기 때문에 max_count 변경 해 주어야 잘 돌아감
}
}
}
}
}
int main() {
short M, K;
scanf("%hd%hd%hd", &N, &M, &K);
for (char i = 0; i < N; i++)
for (char j = 0; j < N; j++) {
scanf("%hd", &tree[i][j].s2d2);
tree[i][j].resource = 5;
}
short x, y, z;
for (char i = 0; i < M; i++) {
scanf("%hd%hd%hd", &x, &y, &z);
tree[--x][--y].level[z] = 1;
tree[x][y].max_level = z;
}
while (K--) {
spring_summer_winter();
}
short cnt = 0;
for (char i = 0; i < N; i++)
for (char j = 0; j < N; j++)
for (char t = 1; t <= tree[i][j].max_level; t++)
if (tree[i][j].level[t])
cnt += tree[i][j].level[t];
printf("%hd", cnt);
}
|
cs |
반응형
'알고리즘 문제 > [백준]' 카테고리의 다른 글
| [백준] 20118번: 호반우가 길을 건너간 이유 (0) | 2020.11.29 |
|---|---|
| [백준] 13907 세금 (2) | 2020.11.05 |
| 백준 16637 괄호 추가하기 (0) | 2020.10.30 |
| 백준 15684 사다리조작 (0) | 2020.10.30 |
| 백준 14500 테트로미오 (0) | 2020.10.30 |