[백준 2248번] [동적 계획법] 이진수 찾기

접근 방법은 다음과 같다.

dp[i][j]를 i번째 자리일 때, j만큼의 1을 가지고 있는 갯수라고 잡았다.

 

따라서 해당 DP의 점화식을

dp[i][j] = sigma(dp[i - k][j - 1]) ( 1 <= k <= i - 1)로 설정하였다.

 

그런데, 조금 비효율적인 것 같아서 타블로그들을 확인해본 결과

dp[i][j]를 i번째 자리까지 처리했을 때 j만큼의 1을 가지고 있는 갯수라고 잡게 되면

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]로 잡으면 된다.

 

이렇게 하게 되면 조금 더 효율적으로 처리할 수 있게 된다.

후자의 방식대로 하면 마지막 문제에서 구하고자하는 이진수로 변환시키는 과정에서 

if 비교해야 하는 대상이 dp[i - 1][j]보다 크면 해당 i에서 1이라는 의미이다. 이 과정을 계속해서 반복해주면 된다.

 

일단 맨 처음 생각한 방식으로 구현한 코드는 다음과 같다.

(처음에 sum을 잘못 처리하는 바람에 엄청나게 해맸다..)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;
typedef long long ll;

ll dp[32][32];

ll N, L, check_num;

void dp_check(int index){
    if(index > N) return;
    if(index == 1){
        dp[index][1] = 1;
        dp[index][0] = 1;
    }
    else{
        for(int i = 1; i <= L; i++){
            if(dp[index][i] != 0) continue; // 이미 처리
            if(i == 1){
                dp[index][i] = 1;
                continue;
            }
            ll sum_result = 0;
            for(int j = 1; j <= index - 1; j++){
                if(dp[index - j][i - 1] != 0){
                    sum_result += dp[index - j][i - 1];
                }
            }
            dp[index][i] = sum_result;
        }
    }
    dp_check(index + 1);
    return;
    
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> L >> check_num;
    memset(dp, 0, sizeof(dp));

    int result_store[32] = {0};

    dp_check(1);

    ll sum_store[32]; // 각 자리기준 몇개가 존재하는지

    int check_count = 0;

    while(check_num){
        for(int i = 1; i <= N; i++){
            ll temp = 0;
            for(int j = 0; j <= L - check_count; j++){
                temp += dp[i][j];
            }
            sum_store[i] = temp;
        }

        ll compare_value = 0;
        if(check_num == 2){
            result_store[1] = 1;
            break;
        }
        if(check_num == 1){
            result_store[1] = 0;
            break;
        }
        for(int i = 1; i <= N; i++){
            compare_value += sum_store[i];
            if(compare_value >= check_num){
                result_store[i] = 1;
                check_num = check_num - (compare_value - sum_store[i]);
                check_count += 1;
                break;
            }
        }
    }

    for(int i = N; i >= 1; i--){
        cout << result_store[i];
    }
    cout << "\n";
    return 0;
}