[BOJ 1038] 감소하는 수(다이나믹 프로그래밍, 수학 풀이)

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

1038번: 감소하는 수

다이나믹 프로그래밍은 For문을 이용하거나, 재귀적으로 함수를 구성하는 것이 아니다. 문제를 나누어서 해결하는 것이다!

 

 

 

 

이 문제가 그러한 특징을 정확히 담고 있다.

 

 

 

 

새로운 감소하는 수를 찾으려면, 기존에 감수하는 수를 이용할 수 있다.

 

 

 

 

기존에 감소하는 수 마지막 자리 수보다 작은 새로운 수를 추가할 수 있으면 된다.

 

 

 

 

위의 알고리즘은 큐를 이용해서 쉽게 구현할 수 있다.

 

 

 

 

해설코드(C++).

 

#include <iostream>

#include <queue>

#include <vector>

 

using namespace std;

 

vector<long long> v;

queue<long long> q;

int N;

 

int main() {

    cin >> N;

    

    v.push_back(0);

    for(int i = 1; i <= 9; i++){

        q.push(i);

        v.push_back(i);

    }

    

    while(!q.empty()){

        long long item = q.front();

        for(int i = 0; i < item % 10; i++){

            q.push(item * 10 + i);

            v.push_back(item * 10 + i);

        }

        q.pop();

    }

    

    if(v.size() <= N)

        cout << -1 << endl;

    else

        cout << v[N] << endl;

    return 0;

}

 

 

 

 

위의 코드와 별개로 수학적 사고(?)로 접근해보자.



0 ~ 9에서 특정한 몇 개를 뽑아서 감소하는 수를 만든다고 생각해보자.


한 개를 뽑아서 조합을 만드는 경우, 10C1
두 개를 뽑아서 조합을 만드는 경우, 10C2
세 개를 뽑아서 조합을 만드는 경우, 10C3
...
열 개를 뽑아서 조합을 만드는 경우, 10C10



고등학교 때 배운 조합의 공식을 이용하면, 총 개수는 (2의 10승  - 1)을 이루게 된다.





비트 마스크를 이용해보자.





0000000000

0123456789




이진수의 각 자리수를 0 ~ 9로 매칭하고, 0은 뽑지 않은 상태, 1은 뽑은 상태라고 정의해보자.





그렇다면, 이진수의 조합으로 우리가 원하는 감소하는 수를 찾을 수 있다.





예를 들어,





0001000101

0123456789

 

위의 상태를 보고, 973으로 변환할수 있도록 값을 코드를 작성해야 한다. 십진수를 이진수로 변환하는 방법을 활용하면 된다.

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
vector<long long> v;
int N;
 
int main() {
    cin >> N;
    for(long i = 1; i <= 1023; i++){
        long long val = i;
        long long temp = 0;
        for(long long j = 9; j >= 0; j--){
            if(val % 2 == 1)
                temp = temp * 10 + j;
            val /= 2;
        }
        
        v.push_back(temp);
    }
    
    sort(v.begin(), v.end());
    if(v.size() <= N)
        cout << -1 << endl;
    else
        cout << v[N] << endl;
    
    return 0;
}