화투의 개발 블로그

문제 링크 : MORSE

문제 링크 : DICT

두 문제 다 같은 개념의 문제이다. 책을 보고도 쉽게 이해가 되지 않아서 머리가 아팠다...

MORSE문제에서의 -를 DICT의 a, o를 DICT의 b로 생각하고 풀면 된다.

이 문제는 k번째 위치에 있는 값을 출력하는 문제인데, 물론 일일이 사전 순서대로 출력하다가, 완성된 부호가 k번째 부호가 아니면, 그 다음 순서의 부호를 찾는 

무식하게 푸는 방법으로도 해결은 가능하다. 근데 문제는 k의 범위가 1억이다. 그냥 무식하게 풀었다가는 시간이 초과될 가능성이 높다.

그래서 여기서 해결하는 방법은, '현재 조합하려는 경우의 수가 찾고자 하는 순서보다 크면 패스, 작으면 찾아나가는' 방법이다.

예를 들어 n개의 -와 m개의 o로 조합을 하는 경우의 수는 이다. 수학을 안한지 오래되어 순열 조합을 까먹어서 기억을 더듬느라 머리가 아팠는데, 복수 순열로 n,m개씩 있을 때, 이를 늘어놓는 경우의 수가이고, 이게  이기 때문이다. 그냥 조합으로 이해하면 될 것 같은데 일단 이렇게 이해하고 넘어갔다...

즉, 현재 구하려는 수가 지금 조합하려는 부호의, 전체 조합 범위에 들어있지 않으면 현재의 구하는 조합의 경우에는 존재하지 않기 때문에, 그 이후는 검색할 필요가 없다는 것이다.

코드 작성 전에 간단한 예를 들어보자.

'-' 2개와 'o' 2개로 조합하는 부호에서, 4번째 수를 찾는다고 하자. 저 요소들로 조합이 가능한 개수는 4C2로, 6가지가 가능하다. 즉, 4번째는 현재 전체 갯수 6개보다 작으므로, 아직 구할 수 있다.

그럼 사전식 순서로 -를 하나 문장에 넣어 이어가보자. 그럼 이제 남은 요소는 '-' 1개와 'o' 2개이다. 이 요소로 가능한 개수는 3C1, 즉 3이다. 

이 말은 첫 글자가 -로 시작하는 문장이 3개(3C1)개라는 말이다. 4번째 문자는, 이 범위를 초과하므로 '-'로 시작하는 것이 아닌 'o'로 시작하는 부호임을 알 수 있다. 

이를 알았으니 이제 '-'가 아닌 'o'로 시작하는 문장중에서, 4-3C1=1번째 시작하는 문장을 찾으면 된다. 이를 지금가지와 같은 방식으로 풀이하면 'o--o'를 구할 수 있다.

밑은 위와 같은 로직으로 구하는 소스코드이다.

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 1000000000+100;
int bino[201][201];

//파스칼의 삼각형으로 조합들을 미리 구해놓는다. 
void calcBino(){
    memset(bino,0,sizeof(bino));
    for(int i = 0; i<=200;++i){
        bino[i][0] = bino[i][i] = 1;
        for(int j = 1; j<i;++j)
            bino[i][j] = min(M, bino[i-1][j-1]+bino[i-1][j]); // 파스칼의 삼각형 점화식
    }
}
int skip;
void gen(int n, int m, string s){
    //기저사례1 : skip이 0보다 작으면 범위를 벗어난 것이므로 리턴한다. 
    if(skip <0) return;
    //기저사례2 : 더이상 조합할 요소가 없으므로 부호 완성. 
    if(n==0&&m==0){
        cout<<s<<endl;
        --skip;
        return;
    }
    //찾고자 하는 수가 현재 조합할수 있는 갯수를 넘어서면, 
    //현재 부호에 존재하지 않으므로 뛰어넘고 반환한다. 
    if(bino[n+m][n]<=skip){
        skip-=bino[n+m][n];
        return;
    }
    //각 요소가 존재하면 조합한다.  
    if(n>0)gen(n-1,m,s+"-");
    if(m>0)gen(n,m-1,s+"o");
}
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    skip = k-1;
    calcBino(); 
    gen(n,m,"");
}

위의 코드는 구하고자 하는 부호가 현재 범위에 포함되는 지의 여부를 재귀 호출로 넘어가서 검사하였지만, 이렇게 할 필요 없이 검사한 후 뛰어넘는 코드를 작성할 수 있다. 그 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int M = 1000000000+100;
int n,m,k,c,bino[201][201];
//파스칼의 삼각형을 통해 조합을 구해놓는다. 
void calcBino(){
    memset(bino,0,sizeof(bino));
    for(int i = 0; i<=200;++i){
        bino[i][0] = bino[i][i] = 1;
        for(int j = 1; j<i;++j)
            bino[i][j] = min(M, bino[i-1][j-1]+bino[i-1][j]); // 파스칼의 삼각형 점화식 
    }
}

int skip = 3;
string gen(int n, int m, int skip){
    //n이 더이상 없으면, o만 존재하므로 m을 반환한다. 
    if(n==0) return string(m,'o');
    
    //'-'를 선택했을경우의 조합의 범위 내에  구하고자 하는 부호를 포함되면
    //'-'를 추가하고 재귀호출한다. 
    if(skip<bino[n-1+m][n-1])
        return "-"+gen(n-1,m,skip);
    //포함되지 않으면 'o'를 추가하고, '-'가 가능한 수만큼 패스하여 다시 검사한다. 
    return "o"+gen(n,m-1,skip-bino[n+m-1][n-1]);
}
int main(){
    cin>>c;
    while(c--){
    cin>>n>>m>>k;
    skip = k-1;
    calcBino(); 
    cout<<gen(n,m,skip)<<endl;
    }
}