Baekjoon 1256번 사전

문제

https://www.acmicpc.net/problem/1256

걸린 시간

03 : 41 : 34

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, m, k;
int dic[201][201]; // n+m, n

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> k;
    memset(dic, 0, sizeof(dic));
    for(int i = 0; i < 201; i++)
        dic[i][0] = 1;
    for(int i = 0; i < 201; i++)
        for(int j = 1; j < 201; j++)
            dic[i][j] = 1;
    for(int i = 2; i < 201; i++)
        for(int j = 1; j < i; j++)
            dic[i][j] = min((dic[i-1][j-1]+dic[i-1][j]), 1000000000);
    if(dic[n+m][n] < k){
        cout << -1;
    }
    else{
        int N = n+m;
        int M = n;
        string ans;
        while(N){
            if(M > 0 && k <= dic[N-1][M-1]){
                ans += 'a';
                M--;
            }
            else{
                ans += 'z';
                k -= dic[N-1][M-1];
            }
            N--;
        }
        cout << ans;
    }
    return 0;
}

문제의 입력조건에 n, m 이 100보다 작거나 같은 자연수라고 되어있다. 자연수에 0이 포함되는지에 대해서 조금 고민해야했는데 문제의 설명을 잘 읽어보면 해답을 찾을 수 있다.

참고

자연수는 0을 포함하나요?