[도전 25일차] 수열 축소 - KOI

※복습 : 

자주 손 씻기!

 

문제 : KOI 2000 고등부 1번 수열축소

코드업/Codeup 4466 수열축소

 

문제 링크

 

사용 알고리즘 : Dynamic Programming

 

지난 포스팅에서 BOJ 수열 축소 문제를 다뤘는데, 

2020/04/24 - [Problem Solving/KOI 고등부] - [도전 24일차] 수열 축소 - 백준

원조 KOI 문제랑 조건이 꽤나 달랐다.

코드업에 KOI 문제가 있길래, 오늘은 이 문제를 다루어 보겠다.

풀이:

이 문제는 CON(i) 연산을 수행 했을 때 단순히 a(i)에서 a(i+1) 를 빼는 것이 아니라, 그 것에 절대값을 취한다. 그렇기 때문에 a2가 무조건 빼진다는 것조차 보장되지 않는다.  

그런데 놀랍게도 이 문제의 경우 n이 30 이하, a의 원소도 30이하로 수의 범위가 매우 작다. 

이를 어떻게 이용할 수 없을까?

 

흠, 이번엔 쉬운 특징을 발견하지 못했다. KOI 공식 풀이를 살짝 들춰 봤다.

 

DT 정의를 참고했다. DT[i][j][k] : 부분수열 ai ~ aj 에 CON 연산을 수행하여 k를 만들 수 있는가?

(모범 사고의 흐름 1.범위가 작다 2. DT를 다차원으로 세워도 된다 3.가능한 걸 다 세워 보자.)

 

호오, 이렇게 되면 문제가 매우 재밌어 진다.

 

DT[i][j][k] : i<=t<j 에 대하여 DT[i][t][x] 와 DT[t+1][j][x±k] 가 모두 true 인  x가 존재하면  true

 

처음엔 a[t]를 뺄 생각만 해서 어 범위가 3개로 분단되네;; 해서 멘붕이 왔는데 생각해보니 그냥 구간을 2개로 쪼개주는 분단점만 정해주면 된다.

 

직관적인 재귀로 코드를 짰다.

DT의 크기는 30*30*30 으로 3만이 채 되지 않으므로 오버헤드를 고려해도 제한 시간 안에 동작한다.

 

역추적을 하는 방법은 다음과 같다.

구간 (i,t)에서 x를 만들고, 구간 (i+1,t)에서 x±k를 만들었다면 이제 CON(i)를 수행하면 된다. 

즉,  (t+1,j) 연산이 끝나고 (i,t) 연산이 끝난 후 CON(i)를 시행하면 된다.

*구간(t+1,j)의 연산을 (i,t)보다 먼저 시행하는 이유를 생각해보면 재밌을 것이다.

이는 별도의 find 함수를 사용하여 해결할 수 있다.

 

반복문으로 구현하면 시간이 훨씬 적게 걸린다.

 

코드

//코드업 4466 수열 축소
#include<stdio.h> 
#include<algorithm>
using namespace std;
int n,T,a[31],DT[31][31][31],flag;
int sign[31][31][31];
int ans[31],cnt; 
int solve(int s,int e,int k){
    if(k<0 || s>e || k>30) return -1;
    if(DT[s][e][k]!=0) return DT[s][e][k];
    if(s==e){
        if(a[s]==k) return 0;
        return -1;
    }
    else if(s+1==e){
        if(abs(a[s]-a[e])==k) return DT[s][e][k]=s;
        return -1;
    }
    for(int t=s;t<e;t++){
        for(int i=0;i<=30;i++){
            int x=solve(s,t,i),y=-1,z=-1;
            if(i>=k) y=solve(t+1,e,i-k);
            if(i+k<=30) z=solve(t+1,e,i+k);
            if(x!=-1&&(y!=-1||z!=-1)){
                sign[s][e][k]=(y!=-1)?i:-i;
                return DT[s][e][k]=t;
            }
        }
    }
    return DT[s][e][k]=-1;
}
void find(int s,int e,int k){
    if(DT[s][e][k]<=0){
        if(s!=e)flag=1;
        return;
    }
    if(s==e) return;
    int x=abs(sign[s][e][k]),y=sign[s][e][k]>0?x-k:x+k;
    find(DT[s][e][k]+1,e,y);
    find(s,DT[s][e][k],x);
    ans[cnt++]=s;
}
int main(){
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    if(T<0||n==1){
        if(T<0 || a[n]!=T) puts("0");
        return 0;
    }
    solve(1,n,T);
    find(1,n,T);
    if(flag || cnt!=n-1)
        puts("0");
    else
        for(int i=0;i<n-1;i++)
            printf("%d\n",ans[i]);
} 

 

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