[BOJ/백준][Gold4] 10836 : 여왕벌 (C++)

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

10836번: 여왕벌

 

 

[난이도] Gold4
[유형] 구현

[풀이]
그냥 구현하면 시간초과가 난다. (1000000*700*2=14억) 의 연산이 필요
=> 최적화가 필요하다.
1. 0,1,2 성장중에서 가장 비중을 많이 차지하는 성장치(a)를 구함
2. 모든 날에 그 a만큼 성장한다고 가정하고 그 모든날에 a만큼 더해줌.
3. 실제로 N개의 입력을 재순회 사면서 성장치가 a인 경우는 스킵하고 a가 아닌 경우에는
그 값으로 수정하는 보정값을 더해준다.
(이 과정으로 시간을 줄이기 때문에 가장 비중을 많이 차지하는 성장치 a를 골랐다. 그 비중만큼 스킵이 가능하기 때문에. 적어도 1/3만큼은 스킵이 가능하다.)
4. 왼쪽열과 행의 최종 값이 업데이트 되었으므로 M*M 배열을 채워준다.

※ 가장 많은 가중치를 구하지 않고 무조건 0을 스킵하는 방식으로 해도 AC를 받을 수 있다고 한다.
※ 누적합 개념을 이용하면 O(N) 의 시간으로 해결이 가능하다. (이게 정해인듯함. 위의 풀이는 O((2*M)/3*N))

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M,map[700][700],t[1400],a[1000000][3],mi;
pair<int,int> cnt[3];
int main(){
    scanf("%d%d",&N,&M);
    
    for(int i=0;i<M;i++){
        for(int j=0;j<3;j++){
            int v;
            scanf("%d",&v);
            cnt[j].second=j;
            cnt[j].first+=v;
            a[i][j]=v;
        }
    }
    sort(cnt,cnt+3);
    mi = cnt[2].second;
    for(int i=0;i<2*N;i++) t[i]=mi*M;
 
    for(int i=0;i<M;i++){
        int k=0;
        for(int j=0;j<3;j++){
            int s=k,e=k+a[i][j];
            if(j!=mi){
               for(int l=s;l<e;l++){
                   t[l]+=(j-mi);
               } 
            }
            k=e;
        }
    }
    int j=0;
    for(int i=N-1;i>=0;i--) map[i][0] = t[j++];
    for(int i=1;i<N;i++) map[0][i] = t[j++];
 
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(i&&j) map[i][j] = max(map[i-1][j-1],max(map[i-1][j],map[i][j-1]));
            printf("%d ",map[i][j]+1);
        }
        puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/10836.cpp