[BOJ] 사전

[문제]

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

1256번: 사전

[풀이]

 

1256

맞았습니다!!

2144 KB

0 ms

C++14 / 수정

1094 B

18분 전

 

1) 조합과 dp를 사용한다. 

 

2) 먼저 사전식 정렬을 생각해보면 알파벳 오름차순으로 정렬된다. (a -> z)

n= 3이고 m= 2일 경우 총 10가지의 경우의 수가 나온다. (n+mCm)

앞에서 6개까지는 a로 시작하는 문자열이고 7-10까지는 z로 시작하는 문자열이다. 

aaazz

aazaz

aazza

azaaz

azaza

azzaa

 

zaaaz

zaaza

zazaa

zzaaa

 

3) k의 범위를 잘 생각해야한다. k가 6보다 작을 경우 a로 시작하는 문자열이 정답이겠고, 아닐 경우 z로 시작하는 문자열일 것이다. 

a로 시작하는 문자열은 K를 다시 조절할 것없이 앞에서 부터 k번째의 문자열을 가져오면 되고, 

k가 6보다 큰 수라면 인덱스를 조절해야 한다. (k - n+mCm)

 

4) dp 이차원 배열에 미리 조합을 구해놓는다. 

nCr = n-1Cr-1 + n-1Cr

 

*조합과 디피라니.. 최악의 조합이었다. 

 

---

#include <iostream>
#define MAX_K 1000000000
using namespace std;
 
//ㅅㅏ전
 
typedef long long ll;
 
int n, m, dp[201][201]; //n = a의 개수 / m = b의 개수 / k번째 문자열
ll k;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    /*
        사전은 a -> z 로 오름차순 정렬 
        조합을 생각해보면 n=2 m=2일 때 
        aazz
        azaz
        azza
        zaaz
        zaza
        zzaa
        -> n+mCm 이다. 
        K는 최대 6이 나올 수 있고, 3개까지는 a로 시작하는 문자열이고 
        그 이후로는 k-n+mCm을 한 값으로 구한다. 
     */
 
    for (int i = 0; i <= (m + n); i++)
    {
        dp[i][0] = 1; //nC0
        dp[i][i] = 1; //nCn
    }
 
    //combination = nCr = n-1Cr-1 + n-1Cr
    for (int i = 2; i <= (n + m); i++)
    {
        for (int j = 1; j < i; j++)
        {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            if (dp[i][j] > MAX_K)
                dp[i][j] = MAX_K; //너무 커지지 않도록 조절
        }
    }
 
    int cnt = 0, size = n + m;
    if (dp[n + m][m] < k)
        cout << "-1" << '\n';
    else
    {
        while (cnt < size)
        {
            if (k <= dp[n + m - 1][m])
            {
                //a로 시작함
                cout << "a";
                n--; //a를 하나 썼으니까
            }
            else {
                k-= dp[n+m-1][m];
                cout << "z";
                m--;
            }
            cnt++;
        }
    }
    return 0;
}