문제

이 문제는 경우의 수를 구하기 위해 조합론을 알면 좋다.

문제 링크

문제 접근

  • 각 자리에 a가 올 경우에 가능한 경우의 수를 세고 k가 그 안에 들어가면 그 자리에 a를 넣고 아니면 z를 넣고 k에서 a가 올 때의 경우의 수를 빼준다.
  • 다음 자리에도 위의 과정을 반복한다.
  • 이때 경우의 수는 조합을 이용한다. a를 선택했을 때의 경우의 수는 (남은 a의 개수 + z의 개수)! / (남은 a의 개수! * z의 개수!)이다.
  • 이 때 조합을 구하는 시간을 단축하기 위해 dp를 이용해서 조합을 미리 구해놓을 수 있다.
  • DP로 조합 계산하기

코드

#include <cstdio>
int N, n, m, k;
unsigned long long nCr[201][201];
int main(){
    scanf("%d %d %d", &n, &m, &k);
    N = n + m;
    nCr[1][0] = 1;    
    nCr[1][1] = 1;
    for (int i = 2; i <= 200; i++){
        nCr[i][0] = 1;
        for (int j = 1; j <= 200; j++){
            nCr[i][j] = nCr[i - 1][j - 1] + nCr[i - 1][j];
        }
    }
    if(nCr[N][n] < k){
        printf("-1");
        return 0;
    }

    for(int i = 0; i < N - 1; i++){
        //a를 선택했을 때의 경우의 수
        if(!n){
            printf("z");
            m--;
            continue;
        }
        unsigned long long x = nCr[n + m - 1][n - 1];
        if(k > x){
            printf("z");
            k -= x, m --;
        }
        else {
            printf("a");
            n --;
        }
    }
    if(n)printf("a");
    else printf("z");
}

느낀점

  • 이 문제를 풀면서 조합론에 대한 수능 강의를 들었다.
  • 수학의 중요성을 다시금 느낀다. 조금씩이지만 계속 공부해놔야겠다!