[BOJ -1256 사전찾기 / 파이썬]

문제 링크 : https://www.acmicpc.net/problem/1256

---

1) 문제 해결

a 가 n개 z가 m개 있다면 이 두개를 나열하는 순열의 개수를 생각해보면

이다. 근데 이 식을 다시 한번 생각해보면 M = (N + M) - N, N = (N +M) - M이므로,

실제 위 식은 n+mCn 이나 n+mCm 과 동일하다.

 

그런데 사전은 a부터 나오므로 a 부터 배치한다고 가정하면 남은 z의 개수를 이용해 점화식을 세우는 편이 더 편하다.

먼저 dp 테이블을 만들어 조합식에 관한 테이블을 미리 생성한다.

조합 테이블을 구하는 점화식은 다음과 같다.

위의 식에서 i, j 를 각각 i개에서 j개를 선택하는 경우의 수라고 생각을 해보자.

만약 데이터가 n개가 있다고 가정했을때 마지막 데이터 전까지 데이터들은 선택됬다고 가정하면 경우의 수는 다음과 같다.

먼저 데이터가 5개 있다고 가정해보자. 그리고 그 중 3개를 선택하는 경우의 수를 구한다고 가정했을때 문제를 다음과 같이 분할해서 생각할 수 있다.

먼저 5개의 데이터에서 4개가 선택되고 마지막 데이터가 남은 상황을 가정해 본다. 그렇다면 앞으로 남은 데이터 5에 대해서 남은 경우의 수는 두가지이다.

1) 5를 선택하지 않았다면 이미 선택된 데이터 4개에서 3가지가 선택된 경우

2) 5를 선택했다면 이미 선택된 데이터 4개에서 2가지가 선택된 경우.

 

따라서 5개중 3개를 선택하는 경우의 수는 (4개의 데이터에서 3가지가 선택된 경우) + ( 4개의 데이터에서 2가지가 선택된 경우와 같다) 이를 바꿔 표현하면

 

C(5, 3) = C(4, 3) + C(4, 2) 파스칼의 삼각형 공식에 관한 점화식과 똑같다.

 

다음 점화식에 따라 테이블을 다음과 같이 초기화 한다.

n, m, k = map(int, input().split()) # 데이터 입력
dp = [[0 for _ in range(n + m + 1)] for _ in range(n + m + 1)]

for i in range(0, n + m + 1):
    for j in range(0, i + 1): # n + m 에서 n이나 m번째를 넘어가기 직전까지만 보면됨.
        if j == 0 or j == i: # n개에서 0개를 선택하는 경우의 수는 1, n개에서 n개를 선택하는 경우의 수도 1
            dp[i][j] = 1
        else:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
            if dp[i][j] > 1000000000:
                dp[i][j] = 1000000001

다음부터는 k 번째 문자를 구하기위해서

현재 자릿수에서 a를 선택했을 때 남아있는 문자들로 만들 수 있는 모든 경우의 수를 T라고 한다.

 

1) a를 선택했을때 남아있는 문자들의 조합해 z를 선택하는 경우의 는 C(n+m-1, m) = T이다 

2) 만약 T가 K 보다 크다면, 현재 문자 자리를 a로 선택한다. 이유는 간단하다. 예를 들어 앞에 a를 고정시키고 가능한 모든 경우의 수가 8가지 인데 3번째 수를 구하라고 한다면 정답은 이 범위 안에 들어있는것이다. 따라서 a를 선택

3) 만약 K가 더 크다면 K 를 K-T로 업데이트 시키고 z 문자를 선택한다. 즉 a를 고정하고 나올수 있는 조합의수가 8가지인데 10번째 수를 구하라 한다면 앞에 이미 나온 8가지를 제거해 준후 나머지 2가지 케이스에 대해서만 고려하면 되는것이다.

 

즉 문자 선택 기준을

1) T >= K : 현재 자리 문자를 a로 선택 a 문자 개수 - 1

2) T < k : 현재 자리 문자를 z로 선택 k = k - t로 업데이트 z 문자 개수 - 1

 

a = 2, z= 2 이고 k = 3이라고 했을때

a를 선택했을 때 나머지 문자열로 만들 수 있는 경우의 수는 D[3][2]

D[3][2] = 3  >= K(=2)므로 a 확정 => z는 2개 남음

D[2][2] = 1 < K(=2)므로 z확정 => z는 1개남음 => K = K - T = 1로 업데이트

아래 다음과 같은 과정 반복

 

if dp[n+m][m] < k:
    print(-1)
else:
    while not (n == 0 and m == 0):
        if dp[n + m - 1][m] >= k:
            print('a', end='')
            n -= 1
        else:
            print('z', end='')
            k -= dp[n + m - 1][m]
            m -= 1

전체 코드는 다음과 같다.

 

n, m, k = map(int, input().split())
dp = [[0 for _ in range(n + m + 1)] for _ in range(n + m + 1)]

for i in range(0, n + m + 1):
    for j in range(0, i + 1):
        if j == 0 or j == i:
            dp[i][j] = 1
        else:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
            if dp[i][j] > 1000000000:
                dp[i][j] = 1000000001

if dp[n+m][m] < k:
    print(-1)
else:
    while not (n == 0 and m == 0):
        if dp[n + m - 1][m] >= k:
            print('a', end='')
            n -= 1
        else:
            print('z', end='')
            k -= dp[n + m - 1][m]
            m -= 1

---

2) 결과