반응형

https://www.acmicpc.net/problem/16235

 

16235번: 나무 재테크

부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 같은 나이의 나무가 많기 때문에 겹치는 나무를 쉽게 관리하기 위해 map 자료 구조를 써서 나무의 개수를 저장합니다.

 

2. 봄과 여름은 동시에 진행 가능하고, 가을과 겨울도 동시에 진행 가능하기 때문에 봄과 여름을 먼저 진행하고, 가을과 겨울을 진행합니다.

 

3. 살아있는 나무의 개수를 세어 ans에 더해줍니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<map>
 
using namespace std;
 
struct tree {
    long long energy = 5;
    int cnt;
    map<int, long long> alive;
    map<int, long long> dead;
};
 
int N, M, K;
int A[11][11];
tree arr[11][11];
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
 
void breeding(int y, int x)    //가을 번식
{
    for (int i = 0; i < 8; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy > 0 && yy <= N && xx > 0 && xx <= N) {
            arr[yy][xx].alive[1] += arr[y][x].cnt;
        }
    }
    arr[y][x].cnt = 0;
}
 
void seasons()    //계절 변화에 따라 map배열 갱신
{
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j].alive.empty()) continue;
            map<int, long long> temp = arr[i][j].alive;
            arr[i][j].alive.clear();
            for (auto it = temp.begin(); it != temp.end(); it++) {    //봄
                int ret = (it->first) * (it->second);
                if (ret <= arr[i][j].energy) {
                    arr[i][j].energy -= ret;
                    arr[i][j].alive[(it->first) + 1] += it->second;
                    if (((it->first) + 1) % 5 == 0) {
                        arr[i][j].cnt += it->second;
                    }
                }
                else {
                    int cnt = arr[i][j].energy / (it->first);
                    arr[i][j].energy -= cnt * (it->first);
                    if (cnt > 0) {
                        arr[i][j].alive[(it->first) + 1] += cnt;
                    }
                    if (((it->first) + 1) % 5 == 0) {
                        arr[i][j].cnt += cnt;
                    }
                    arr[i][j].dead[it->first] = (it->second) - cnt;
                }
            }
 
            temp = arr[i][j].dead;    //여름
            for (auto it = temp.begin(); it != temp.end(); it++) {
                arr[i][j].energy += (it->first/2) * (it->second);
            }
            arr[i][j].dead.clear();
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j].cnt) {
                breeding(i, j);    //가을
            }
            arr[i][j].energy += A[i][j];    //겨울
        }
    }
}
 
int main()
{
    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]);
        }
    }
 
    for (int i = 0; i < M; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        arr[x][y].alive[z]++;
    }
 
    for (int i = 0; i < K; i++) {
        seasons();
    }
 
    int ans = 0;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (auto it = arr[i][j].alive.begin(); it != arr[i][j].alive.end(); it++) {
                ans += it->second;
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 5373번 - 큐빙 (C++)  (0) 2022.09.15
[ 백준 ] 17140번 - 이차원 배열과 연산 (C++)  (0) 2022.09.14
[ 백준 ] 15685번 - 드래곤 커브 (C++)  (0) 2022.09.12
[ 백준 ] 15683번 - 감시 (C++)  (0) 2022.09.11
[ 백준 ] 15684번 - 사다리 조작 (C++)  (0) 2022.09.10

+ Recent posts

티스토리툴바