모스 부호 사전

문제링크: 모스 부호 사전

동적계획법 문제를 풀 때 유형이 있다.

K번째 답을 찾는 것이라면,

1. 완전정복으로 푼다.

2. skip할 수 있는 지 줄여본다. (이항계수 등으로)

3. 문제 자체를 한번에 풀 수 없는 지 생각해본다. 

위와 같은 순서로 해본다. 

K번째 답을 구할 때에는 

N개에서 M개를 뽑는 가짓수를 이용해서 할 수 있는지 생각한다.

nCm = n-1Cm + n-1Cm-1 임을 이용한다!!! 

n: 1, m:0으로 생각.

 

#include <iostream>
#include <string>
using namespace std;
int N = 2, M = 3;
void solve(int n, int m, string s) {
    if (n == 0 && m == 0) {
        cout << s << endl;
        return;
    }
    if(n>0) solve(n - 1, m, s + '0');
    if(m>0) solve(n, m - 1, s + '1');
}
 
void main() {
    string s = "";
    solve(N, M, s);
    return;
}

을 호출 하면, 0 n개, 1 m개를 뽑는 가짓수를 오름차순으로 출력한다. 

solve는 iostream만을 이용해서 recursive로 call하면서 n+mCn 개를 넘으면 트리의 하위 가짓수를 call하지 않고

뛰어 넘도록 짠 코드이다. 

solve2의 경우는 모든 경우의 수를 돌면서 계산하고 skip하는 solve함수의 방식이 아니라,

각자리를 하나하나 결정하고 넘어가는 방식이다. 

n+mCn 개에서 K가 m+n-1에서 n-1개를 선택한 것보다 크면, n을 하나 선택했으므로, 1을 선택하고, m-1개만 고르면 되도록 함수를 호출하고,

작으면 그 범위에 있으므로, 0를 선택하고, n-1개 m개를 선택하도록 함수를 호출하면 된다. 

#include <iostream>
#include <string>
using namespace std;
#define min(a,b) (a)<(b) ? (a):(b)
int C, N, M, K;
int index;
char moss[201];
const int MAX = 1000000000;
const char A = 45; //-
const char B = 111;     //o
string moss2;
int top = 0;
int bino[1000][1000];
 
void binomial(int num) {
    bino[1][0] = bino[1][1] = 1;
    for (int i = 2; i < num; i++) {
        bino[i][0] = bino[i][i] = 1;
        for (int j = 1; j < i; j++) {
            bino[i][j] = min(MAX, bino[i - 1][j] + bino[i - 1][j - 1]);
        }
    }
}
 
void solve2(int n, int m, string s) {
    if (n == 0) {
        for (int i = 0; i < m; i++)
            s += B;
        cout << s << endl;
        return;
    }else if(m==0) {
        for (int i = 0; i < n; i++)
            s += A;
        cout << s << endl;
        return;
    }
    int skip = bino[m + n - 1][n - 1];
    if (K > skip) {
        K -= skip;
        solve2(n, m - 1, s + B);
    }
    else {
        solve2(n - 1, m, s + A);
    }
 
}
void solve(int n, int m, char *s) {
    if (n == 0 && m == 0) {
        K--;
        if (K == 0) {
            for (int i = 0; i < (M + N); i++) {
                cout << moss[i];
            }
            cout << endl;
        }
 
        return;
    }
 
    int skip = bino[n+m][n];
    if (K > skip) {
        K -= skip;
        return;
    }
    if (K < 0)
        return;
    if (n > 0) {
        moss[top++] = A;
        solve(n - 1, m, moss);
        top--;
    }
    if (m > 0) {
        moss[top++] = B;
        solve(n, m - 1, moss);
        top--;
    }
 
}
 
int main() {
    freopen("input.txt", "r", stdin);
 
    cin >> C;
    binomial(200);
 
    for (int c = 0; c < C; c++) {
        cin >> N >> M >> K;
        top = 0;
        index = 0;
        //solve(N, M, moss);
        solve2(N, M, moss2);
    }
    return 0;
}