×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,191,305명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 구현

2. 규칙


이 문제는 하라는 순서대로만 잘 지켜서 문제를 풀면 된다.


봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.


여름에는 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.


가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 어떤 칸 (r, c)와 인접한 칸은 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1) 이다. 상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.


겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.


위의 계절별 상태는 항상 순차적으로 이루어져야하고

특히 봄에 나무가 죽었다해서 바로 양분을 /2해서 더해주면 봄의 상태에 영향을 끼치게 된다.


나머지는 아래 주석을 통해 상태에 따라 자세히 설명해두었다.








소스 코드 : 



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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <memory.h>
 
using namespace std;
 
int land[12][12];
vector<int> tree[12][12];
int summer[12][12];
int winter[12][12];
 
int dy[8= { -1,-1,-1,0,0,1,1,};
int dx[8= { -1,0,1,-1,1,-1,0,};
 
int main() {
    int n, m, k;
    scanf("%d %d %d"&n, &m, &k);
 
    // 놀랍게도 양분은 모든 칸이 5만큼 들어있었다.
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            land[i][j] = 5;
            scanf("%d"&winter[i][j]);
        }
 
    // r과 c는 1부터 시작한다.
    for (int i = 0; i < m; i++) {
        int y, x, age;
        scanf("%d %d %d"&y, &x, &age);
        y--, x--;
        tree[y][x].push_back(age);
    }
 
    while (k--) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!tree[i][j].empty()) {
                    // 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
                    sort(tree[i][j].begin(), tree[i][j].end());
                    for (int t = 0; t < tree[i][j].size(); t++) {
                        int cur = tree[i][j][t];
 
                        // 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 
                        // 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다.
                        if (cur <= land[i][j]) {
                            land[i][j] -= cur;
                            tree[i][j][t]++;
                        }
                        // 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 
                        // 양분을 먹지 못하고 즉시 죽는다.
                        // 봄에 죽은 나무가 양분으로 변하게 된다. 
                        // 소수점 아래는 버린다.
                        else {
                            tree[i][j].erase(tree[i][j].begin() + t);
                            summer[i][j] += (cur / 2);
                            t--;
                        }
                    }
                }
            }
        }
        
        // 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                land[i][j] += summer[i][j];
 
        memset(summer, 0sizeof(summer));
 
        vector<int> tmpTree[12][12];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int t = 0; t < tree[i][j].size(); t++) {
                    tmpTree[i][j].push_back(tree[i][j][t]);
                }
 
        // 가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 
        // 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
 
                for (int t = 0; t < tree[i][j].size(); t++) {
                    if (tree[i][j][t] % 5)
                        continue;
 
                    for (int q = 0; q < 8; q++) {
                        int ny = dy[q] + i;
                        int nx = dx[q] + j;
 
                        if ((<= ny && ny < n) && (<= nx && nx < n))
                            tmpTree[ny][nx].push_back(1);
                    }
                }
            }
        }
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                tree[i][j].clear();
                for (int t = 0; t < tmpTree[i][j].size(); t++)
                    tree[i][j].push_back(tmpTree[i][j][t]);
            }
 
        // 겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 
        // 각 칸에 추가되는 양분의 양은 A[r][c]
        for (int i = 0; i < n; i++
            for (int j = 0; j < n; j++
                land[i][j] += winter[i][j];
    }
 
    // K년이 지난 후 상도의 땅에 살아있는 나무의 개수
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ans += tree[i][j].size();
 
    printf("%d\n", ans);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[16956번] 늑대와 양  (0) 2019.03.03
[16234번] 인구 이동  (4) 2018.10.22
[16235번] 나무 재테크  (0) 2018.10.22
[16236번] 아기 상어  (4) 2018.10.21
[14890번] 경사로  (0) 2018.09.27
[1038번] 감소하는 수  (0) 2018.09.25