[도전 24일차] 수열 축소 - 백준

※복습 : 

 

문제 : 백준 2237 수열 축소

문제 링크

 

사용 알고리즘 : Dynamic Programming

 

풀이: 

1. CON 연산에 쫄 필요 없다.

n=3, n=4인 경우에 해보면 대충 감이 잡힌다.

n=4일 때 T로 가능한 값은

a1 - a2 - a3 - a4

a1 - a2 - a3 + a4

a1 - a2 + a3 - a4

a1 - a2 + a3 + a4 로 총 4가지다. 

a1은 무조건 더해야 하고, a2는 무조건 빼야 한다. 그리고 뒤에 것들은 어떤 부호이든 가능한 것이 핵심이다.

어떤 수열에 대해서 2번째 지점에 오는 친구는 무조건 빼야 되는게 핵심이다.

CON(1)을 실시하면 a3를 a2로 땡겨오게 된다.  그러면 이제 a3도 빼야 한다. 

CON(2)를 실시하면 a3을 a2에서 뺀다. 그런데, a2에 있는 값은 나중에 어떻게 하든 빼게 되므로 a3은 더해지게 된다.

 

i번째 실시하는 CON(1)은 a(i+2) 를 빼는 것, CON(2)은 a(i+2)를 더하는 것이다.  

 

즉, N-1번의 CON 연산 중 CON(1) 과 CON(2) 만을 이용하여 가능한 모든 T를 만들 수 있다는 것이다.

 

가능한 모든 T를 구하는 것은 부서배치와 같은 DT 기법을 사용하여 해결할 수 있다.

 

DT[i][j] : a1~ai 까지 보았을 때 j를 만들려면 ai를 어떻게 해야 하는가?

0 : j를 만들 수 없다.

1 : CON(1) 을 실시해야 한다.

2 : CON(2) 를 실시해야 한다.

 

DT[i][j] 가 true 이면 DT[i+1][j-a[i+1]] = 1 , DT[i+1][j+a[i+1]] = 2 로 체크해주면 된다.

 

Initialize : DT[2][a[1]-a[2]] =1 

 

여기서 몇가지 최적화를 시켜줄 수 있는데,

1. 항상 가능한 축소 연산이 존재하며, 2. DT에 들어갈 값은 0,1,2밖에 없으므로

bitset 2개를 사용하는 것으로 메모리를 훨씬 적게 사용할 수 있다.

 

DT를 채울 때 ,a1~ai까지 보면 가능한 가장 작은 값은 모든 ai를 뺀 것, 가장 큰 값은 모든 ai를 더한 값임을 알 수 있다. 즉, j의 하한과 상한을 정해 시간을 줄일 수 있다.

코드

//https://howtoliveworldnice.tistory.com/110
#include<stdio.h>
#include<bitset>
using namespace std;
int n,T,a[101];
const int M = 10000;
int main(){
    bitset<20001> DT[101]; //-10000 ~ 10000
    bitset<20001> move[101];
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    DT[2].set(a[1]-a[2]+M);
    int lb=a[1]-a[2],rb=a[1]-a[2]; 
    //a1~ai까지 보았을 때 만들 수 있는 가장 작은 값고 큰 값.
    for(int i=2;i<n;i++){
        for(int j=lb;j<=rb;j++){
            if(DT[i].test(j+M)){
                DT[i+1].set(j-a[i+1]+M);
                DT[i+1].set(j+a[i+1]+M);
                move[i+1].set(j+a[i+1]+M);
            }
        }
        lb-=a[i+1]; rb+=a[i+1];
    }
    int ans[101],id=n;
    T+=M;
    ans[n-1]=1; //a2는 어차피 빼야 하므로 마지막에 실시해준다. 
    while(id>2){
        ans[id-2]=move[id][T]+1;
        T+=a[id]*(ans[id-2]==1?1:-1);
        id--;
    }
    for(int i=1;i<=n-1;i++)
        printf("%d\n",ans[i]);
}

 

궁금한 점이 있으시다면 질문 남겨주세요 :)