[백준] 나무 재테크 16235번 (c++) deque, 특정 조건을 활용한 정렬 제거

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

 

풀이 방법

처음에는 현재 나무를 모두 vector에 저장해서 매번 여름마다 정렬을 했다. 

처음 생각엔 정렬 시간 복잡도는 nlogn이라 생각했기 때문에 시간적 여유가 있을 것이라 생각하고 제출했더니 시간초과가 발생했다.

다른 분들의 풀이를 보니 deque를 사용해서 정렬을 하지 않는 것이 시간이 덜 드는 것을 알 수 있었다. 

deque방법을 봤을 땐, for i = 0 ~ n, for j = 0 ~ n 즉 n^2의 시간 복잡도가 걸린다 생각해서 정렬을 하는 것이 시간이 덜 든다고 생각했지만, n의 최댓값은 11이고 정렬을 하게 된다면 나무의 개수가 121개만 넘어가더라도 deque를 활용하는 것이 더 효율적이라는 것을 알 수 있었다. 

 

deque를 사용해서 각 위치에 해당하는 나무를 저장했다. 즉 deque<int> tree[11][11]을 설정했다. 

 

deque를 사용하면 정렬을 안해도 되는 이유는 나무가 번식할 때 나이가 1이라 정해져 있으므로, deque의 앞에 추가해 주면 된다.

그렇게 되다면 자동으로 정렬이 된다.

 

이 과정만 해결한다면 단순 구현이다.

 

#include<iostream>
#include<memory.h>
#include<vector>
#include<algorithm>
#include<deque>


// 데큐를 사용해서 정렬 줄이기
// 
using namespace std;

int n, m, k; // 땅크기, 나누의 갯수, k년 후

int A[11][11];
int ground[11][11];
int dy[8] = {0, 0, 1, -1, 1, 1, -1, -1}; // 주변 8방향
int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
deque<int> tree[11][11]; // 각 배열의 나무를 저장한 deque

void Input() {
    cin >> n >> m >> k;

    for (int i = 0;i < n;i++) {  // 입력 받기
        for (int j = 0;j < n;j++) { //초기 값 5
            cin >> A[i][j];
            ground[i][j] = 5;
        }
    }   

    for (int i = 0;i < m;i++) {
        int a, b, c;
        cin >> a >> b >> c; //x , y, age
        tree[a-1][b-1].push_front(c);        
    }
}

void spring_summer() {
    //봄에는 자신의 나이만큼 양분을 먹고 나이 1증가한다.
    // 한 칸에 여러개라면 어린 나무 부터 먹는다.
    // 양분을 먹지 못하면 즉시 죽는다.    
    for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				int size = tree[i][j].size();
				// 양분 먹고 나이 +1
				int k =  0;
				for(; k < tree[i][j].size(); ++k) {
					if (ground[i][j] >= tree[i][j][k]) {
						ground[i][j] -= tree[i][j][k];
						tree[i][j][k]++;
					} else {
						break;
					}
				}
				// 여름
				// 죽은 나무 있는 곳 양분 추가
				for(int p = tree[i][j].size() - 1; p >= k; --p) {
					ground[i][j] += tree[i][j][p] / 2;
					tree[i][j].pop_back();
				}
			}
		}


    return ;
}


void fall() {
    // 가을에는 나무가 번식한다.
    // 나이가 5의 배수인접한 8개의 칸에 1인 나무가 생성된다. 
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            for (int k = 0;k < tree[i][j].size();k++) {
                if (tree[i][j][k] % 5 == 0) {

                    for (int z = 0;z < 8;z++) {
                        int ny = i + dy[z];
                        int nx = j + dx[z];
                        if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
                        tree[ny][nx].push_front(1); // 나무 추가
                    }
                }
            }
        }
    }    
    return ;
}

void winter() {
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            ground[i][j] += A[i][j];
        }
    }
    return ;
}

int main() {    
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    Input();    
    for (int i = 0;i < k;i++) {
        spring_summer();        
        fall();
        winter();
    } 
    int ans = 0;
    for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if (tree[i][j].size() > 0) {
				ans += tree[i][j].size();
			}
		}
	}
    cout << ans;
    return 0;
}