[BOJ 1256] 사전

이 문제는, 조합에 대한 고등학교 공식을 알아야 풀 수 있다.

 

 

 

C(N, M) = C(N - 1, M - 1) + C(N - 1, M)

 

 

 

이 식으로, K의 범위를 체크할 수 있다. 하지만, 단어를 찾기 위해서는 하나 더 생각할 필요가 있다.

 

 

 

1) a _ _ _ _

2) z _ _ _ _

 

 

 

위와 같은 형태가 있을 때, K와 대소관계에 따라서 1), 2) 중 하나가 선택된다.

 

 

 

만약 N이 2, M이 3이라고 하면,

 

 

 

1)이 되려면 K <= C(N + M - 1, M)

2)는 1)에 해당되지 않으면 2)가 된다. K에서 C(N + M - 1, M)을 빼줘야 한다. 

 

 

 

위의 형태를 일반화해서 FOR문을 작성하면 된다.

 

 

 

 

해설코드(C++).

#include <iostream>
using namespace std;
 
int N, M, K;
int C[201][101];
string answer;
 
int main() {
    cin >> N >> M >>K;
    
    C[0][0] = 1;
    for(int i = 1; i <= N + M; i++){
        C[i][0] = 1;
        for(int j = 1; j <= M && j <= i; j++){
            if(i == j) {
                C[i][j] = 1;
                continue;
            }
            
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
            if(C[i][j] >= 1000000000) C[i][j] = 1000000000;
        }
    }
    
    K--;
    if(C[N + M][M] <= K) 
        cout << -1 << endl;
    else{
        for(int i = N + M - 1; i >= 0; i--){
            if(i >= M && C[i][M] > K)
                answer = answer + "a";
            else{
                answer = answer + "z";
                K -= C[i][M];
                M--;
            }
        }
        cout << answer << endl;    
    }
    return 0;
}