[C++] 백준 10836 여왕벌

 

#include <iostream>
#include <algorithm>
 
using namespace std;
int n,m;
int arr[701][701];
int dx[] = {0,-1,-1};
int dy[] = {-1,-1,0};
int v[1500];
 
void input() {
    cin >> m >> n;
    
    for(int i=0; i<=700; i++) {
        for(int j=0; j<=700; j++) {
            arr[i][j] = 1;
        }
    }
        
    while(n--) {
        int a,b,c;
        cin >> a >> b >> c;
        int cnt = 0;
        for(int i=0; i<a; i++) {
            v[cnt] = v[cnt] + 0;
            cnt++;
        }
        
        for(int i=0; i<b; i++) {
            v[cnt] = v[cnt] + 1;
            cnt++;
        }
        
        for(int i=0; i<c; i++) {
            v[cnt] = v[cnt] + 2;
            cnt++;
        }
    }
}
 
void solve() {
    int tmp = 0;
    for(int i=m-1; i>=0; i--) {
        arr[i][0] = 1 + v[tmp++];
    }
    for(int i=1; i<m; i++) {
        arr[0][i] = 1 + v[tmp++];
    }
    
    for(int i=1; i<m; i++) {
        for(int j=1; j<m; j++) {
            int max_tmp = 0;
            for(int k=0; k<3; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                max_tmp = max(max_tmp,arr[nx][ny]);
            }
            arr[i][j] = max_tmp;
        }
    }
    
}
 
void print() {
    for(int i=0; i<m; i++) {
        for(int j=0; j<m; j++) {
            cout << arr[i][j] << " ";
        }
        cout << "\n";
    }
}
 
int main() {
    input();
    solve();
    print();
    
}

아이디어를 생각해내면 쉽게 풀 수 있는 문제 

 

날짜 수는 1,000,000 이고 가로 세로가 700 이므로 날짜 하루당 모든 배열을 초기화 해주면 O(1,000,000 * 50,000) 으로 시간초과가 나게 될 것이다.

 

결국 O(1,000,000) 으로 처리를 해야하는데 어떻게 해야할까??

 

1. 여왕벌이 자라는 값은 고정값이므로 위치에 따른 증가값을 누적해서 갱신해준다.

2. N번 만큼 갱신이 끝났으면 증가값을 왼쪽 아래 부터 차례대로 더해준다

3. 1,1 부터 시뮬레이션 알고리즘을 이용해 완전탐색 해서  좌, 좌상, 상 세가지 값중 가장 큰 값을 찾아 갱신해준다.

 

결국 제일 왼쪽 열과 제일 위쪽 행을 초기화 하고 (1,1) 부터 탐색하면 좌, 좌상, 상 세가지 값을 탐색할 수 있다.