백준 5900번 Cow IDs

문제 링크입니다: https://www.acmicpc.net/problem/5900

조합을 이용하여 풀어주면 되는 문제였습니다.

알고리즘은 아래와 같습니다.

1. M 자리 수에서 '1'이 K개 있는 경우의 수가 총 몇개인지 DP를 통해 구해줍니다.(조합)

2. '1'이 K개일 때 몇 자리수에서 N 등 이상인지를 파악합니다.

3. 재귀를 이용하여 해당 등 수 숫자를 구해줍니다.

i) digit 자리수이고 '1'이 K개일 때의 경우의 수보다 N이 높으면 해당 자리에 1을 추가하고 해당 등수만큼 N에서 빼준 뒤 재귀 호출을 해줍니다.

ii) digit 자리수이고 '1'이 K개일 때의 경우의 수보다 N이 작거나 같으면 해당 자리에 0을 추가하고 재귀 호출 해줍니다.

*정해에서는 MAX를 5000으로 잡았는데 5000C2가 대략 10,000,000 근처의 수여서 그렇게 잡은 것 같습니다.

#include <iostream>

#include <string>

using namespace std;

 

const int MAX = 10000;

 

string result;

int cache[10 + 1][MAX + 1]; //K, 자리수

 

void calc(int digit, int K, int N)

{

        //기저 사례

        if (digit == 0)

                 return;

 

        if (N <= cache[K][digit - 1])

        {

                 result += '0';

                 calc(digit - 1, K, N);

                 return;

        }

 

        //N > cache[K][digit - 1]

        N -= cache[K][digit - 1];

        result += '1';

        calc(digit - 1, K - 1, N);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, K;

        cin >> N >> K;

 

        if (K == 1)

        {

                 string s = "1";

                 for (int i = 0; i < N - 1; i++)

                         s += '0';

                 cout << s << "\n";

        }

        else

        {

                 int digit;

 

                 cache[0][0] = 1;

                 for (int j = 1; j <= MAX; j++)

                 {

                         cache[0][j] = 1;

                         //조합

                         for (int i = 1; i <= K; i++)

                         {

                                 cache[i][j] = cache[i][j - 1] + cache[i - 1][j - 1];

                                 //오버 플로우 방지

                                 if (cache[i][j] > 10000000)

                                          cache[i][j] = 10000000;

                         }

 

                         //자리수 파악

                         if (cache[K][j] >= N)

                         {

                                 digit = j;

                                 break;

                         }

                 }

 

                 calc(digit, K, N);

                 cout << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~