[ 백준 16235 ] 나무 재테크 (C++)

[문제보기]

 

[해결과정]

 1. 2차원 vector로 맵 구현 (arr), 현재 양분 상태 저장 맵(map), S2D2 기계가 추가할 양분 맵 (mapS) 구현

 2. 양분 상태의 초기값은 5, S2D2 양분 입력받기

 3. 나무 입력받기 (y, x, age) 순으로...

 

 4. 봄, 여름, 가을, 겨울 구현하기 (봄과 여름은 함께 구현)

   - 봄, 여름 : arr[i][j].size() 가 0이 아니라면, 나무가 있는 상태 이므로 접근, arr vector를 오름차순으로 정렬 후 임시 vector를 하나 만들어주고, 현재 나무의 나이와 양분 상태를 체크하여 양분이 충분하다면 양분 맵은 나무의 나이만큼 줄여주고, 임시 vector에 추가. 만약 나이만큼 되지 않는다면 death 변수에 나무의 나이/2 만큼 더함. 모든 작업이 끝나면 기존 arr vector는 clear하고, 임시 vector 내용을 복사함. 그리고 map에 death의 총합을 더함.

   - 가을 : arr[i][j].size() 가 0이 아니라면, 나무가 있는 상태 이므로 접근, 나무 하나하나를 조사하며 %5 ==0 이라면 주변에 나무 1개씩 추가

   - 겨울 : map에 mapS만큼 더해줌

 

<사진> 문제 해결 시 설계 필기

[소스코드]

#include<iostream>
#include<vector>
#include<memory>
#include<algorithm>
#include<queue>
#include<deque>
using namespace std;
const int MAX = 12;
 
int n, m, k;
vector<int> arr[MAX][MAX];
int map[MAX][MAX];
int mapS[MAX][MAX];
 
int dy[8] = { -1,-1,-1,0,0,1,1,1 };
int dx[8] = { -1,0,1,-1,1,-1,0,1 };
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < n;
}
 
void func() {
    // 봄, 여름
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j].size() == 0) continue;
            sort(arr[i][j].begin(), arr[i][j].end());
 
            vector<int> temp;
            int death = 0;
 
            // 현재 위치의 나무 갯수
            for (int s = 0; s < arr[i][j].size(); s++) {
                int nowTree = arr[i][j][s];
                
                if (map[i][j] >= nowTree) {
                    temp.push_back(nowTree + 1);
                    map[i][j] -= nowTree;
                }
                else {
                    death += nowTree / 2;
                }
            }
 
            map[i][j] += death;
            arr[i][j].clear();
            for (int s = 0; s < temp.size(); s++) {
                arr[i][j].push_back(temp[s]);
            }
 
        }
    }
 
 
    // 가을
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j].size() == 0) continue;
            for (int s = 0; s < arr[i][j].size(); s++) {
                if (arr[i][j][s] % 5 == 0) {
                    int ny, nx;
                    for (int o = 0; o < 8; o++) {
                        ny = i + dy[o];
                        nx = j + dx[o];
                        if (inside(ny, nx)) {
                            arr[ny][nx].push_back(1);
                        }
                    }
                }
            }
        }
    }
 
    // 겨울
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] += mapS[i][j];
        }
    }
 
}
 
int main() {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> mapS[i][j];
            map[i][j] = 5;
        }
    }
 
    int y, x, age;
    for (int i = 0; i < m; i++) {
        cin >> y >> x >> age;
        arr[y-1][x-1].push_back(age);
    }
 
    for (int i = 0; i < k; i++) {
        func();
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            //if (arr[i][j].size() == 0) continue;
            ans += arr[i][j].size();
        }
    }
 
    cout << ans << "\n";
 
 
    return 0;
}
 

 

[해결 과정 중 실수한 부분]

 단순 시뮬레이션 문제다. 시뮬레이션 문제에서의 팁은, 실수를 하지 않는 것! 위 문제를 해결 할 때 도 변수 실수를 해서 10분간 해맸다;... 또한, STL 사용법을 익히는 것이 중요한 것 같다. STL에 대한 숙지가 제대로 되어있지 않아, 몇 가지는 인터넷 검색을 통해 찾았다.. 물론 위 문제에서 검색했던 STL로 해결하지 않았다...

 

[관련 문제 혹은 비슷한 문제]

 삼성 역량테스트