백준 11883 생일수 I

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

11883번: 생일수 I

전형적인 다이나믹 프로그래밍 문제이다. 다만 몇 가지 신경 쓸 부분이 있다.

 

예제에서 주어진 11을 보자.

11은 3+8=11 이어서 38로 생일수를 만들 수 있다.

이 문제를 풀기 위해서는 3, 5, 8을 차례대로 활용하여 합산 해나가 11을 완성하면 된다고 생각할 수 있다.

dp[i]자리에 3, 5, 8등을 넣어주고, dp[목표값]을 읽어서 그 자리에 8이 있다면, dp[목표값-8]을 읽는다. 이런 식으로 i가 0이 될 때까지 읽어둔 수들을 역순으로 출력하면 답이 되는 것이다.

 

그리고 매 테스트케이스마다 새로 연산을 할 필요는 없다. 어떠한 값이 주어지더라도 그 값을 만드는 가장 짧은 길이의 생일수는 유일하기 때문이다. 따라서 미리 DP테이블(배열)을 완성해두고, 주어진 값을 받아 바로바로 답을 pop 해주면 된다.

 

필자가 처음에 생각한 것은 dp[i]가 비어있다면(0이라면) 채워주고, 다른 값이 들어오지 못하게 하는 것이었다. 

즉, 0에서부터 문제에서 정한 자연수 N의 상한까지 루프로 순회를 하면서,

•  i+3 / i+5 / i+8 이 상한값을 넘지 않는지 확인 (인덱스 에러 방지)
• 해당 dp[i+3]이 비어있는지 확인 (0인 건지?)  <--- 이 부분이 잘못되었다.
• 위의 2가지 조건을 만족했다면 해당 위치에 3, 5, 8중의 하나(이번에 사용한 것)를 입력

아래에서부터 차례로 더해주어도, 어떠한 값에 도달하였을 때는 그 길이가 가장 짧을 것이라고 생각한 게 잘못이었다.

그래서 반례로는 20을 생각할 수 있다.

20의 생일수는 5555이다. 하지만 위와 같은 방식으로는 33338이 나온다. 12를 15보다 먼저 방문하기에 12+8을 했을 때 dp[20]이 채워지게 되는 것이다! 그래서 이런 문제를 방지하기 위해 큐를 사용할 수 있다. 큐에 들어있는 만큼 빼는 식으로 처리하면 최단길이를 보장할 수 있게 되는 것이다. 하지만 필자는 그냥 큐를 사용하지 않고 풀어보고 싶었다...

 

그러려면 2차원 배열을 도입하면 된다. dp[i][2]

dp[i][0]은 이제 합산했을 때 i를 만드는 생일수의 마지막 수가 들어있게 되고, dp[i][1]에는 지금까지 몇 번 더했는지 횟수가 담긴다.

즉, dp[i+3][1] > dp[i][1]+1 이어야만 dp[i+3][0]=3을 쓸 수 있게 된다. 

이렇게하면 dp[20][1]=5, dp[20][0]=8 로 처음에 쓰여지겠지만, 이후에 dp[15+5][1]=4, dp[15+5][0]=5로 바뀌게 된다.

 

다이나믹 프로그래밍은 brute force로는 O(n^2) 같아보이는 연산을 O(n)으로 줄여주는 경우가 많다. 그게 가능한 이유는 수많은 중복연산에 대한 처리가 내재되어있기 때문이다. 보통 여러 번 방문하는 (중첩되는) 어떤 정점에서 특정한 처리를 함으로써 문제를 해결한다. 이 문제에서는 생일수의 길이가 비교인자가 되었다. 12에서 8을 더해도 20이 되고, 15에서 5를 더해도 20이 되고, 17에서 3을 더해도 20이 된다. n제곱의 연산 방식에서는 매번 새로운 출발을 해야했을 것이다. 하지만 다이나믹 프로그래밍에서는 생일수의 길이를 계속 추적해서, 그 길이가 더 큰 경우는 과감히 버린다. 그래서 15+5=20인 경우만 살아남게되고, 이후 20에서 출발하여 도달하는 수는 항상 5555를 앞에 갖게 된다.

 

<주요 알고리즘>

다이나믹 프로그래밍

 

<코드>

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

const int sz=1e6+5;
int dp[sz][2],t,n;
vector<int>nums;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    dp[0][0]=1;
    for(int i=0;i<sz;++i){
        if(!dp[i][0])continue;
        if(i+3<=sz&&(!dp[i+3][0]||dp[i][1]+1<dp[i+3][1])){
            dp[i+3][0]=3;
            dp[i+3][1]=dp[i][1]+1;
        }
        if(i+5<=sz&&(!dp[i+5][0]||dp[i][1]+1<dp[i+5][1])){
            dp[i+5][0]=5;
            dp[i+5][1]=dp[i][1]+1;
        }
        if(i+8<=sz&&(!dp[i+8][0]||dp[i][1]+1<dp[i+8][1])){
            dp[i+8][0]=8;
            dp[i+8][1]=dp[i][1]+1;
        }
    }
    dp[0][0]=0;

    cin>>t;
    while(t--){
        cin>>n;
        nums.clear();
        if(!dp[n][0]){
            cout<<-1<<endl;
            continue;
        }
        while(n){
            nums.push_back(dp[n][0]);
            n-=dp[n][0];
        }
        for(int i=nums.size()-1;i>-1;--i)cout<<nums[i];
        cout<<endl;
    }
    return 0;
}