[백준] 사전

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

1256번: 사전

다이나믹 프로그래밍을 이용하는 문제입니다. 

 

우선 문제부터 간단히 요약하면, 

a의 갯수 M, z의 갯수 N이 주어질 때, 사전형태로 나열 했을 경우, K 번째 문자열을 return 해야 합니다. 

 

메모리제한이 생각보다 작게 걸려 있어서 combination을 저장해서 하는 방식에서는 메모리 초과가 나왔는데 두가지 방법 모두 설명해 보겠습니다. 

 

<Solution - 오답>

우선 조합을 이용하기 위해 피보나치 수열을 dp table로 구성해서 만들었습니다. 다음으로 a의 갯수 + z의 갯수 만큼의 z array를 만들고, 0~10의 수를 combination을 이용하여 뽑아서 해당하는 index를 변형시키는 형태로 구현하였습니다. 

실제 구현은 아래와 같습니다. 하지만 이렇게 구현하는 경우, array를 이용한 combination을 저장하는 공간으로 인해 메모리 초과가 나게 됩니다. 

import sys
import itertools

n, m, k = map(int,sys.stdin.readline().rstrip().split())

# calculate total posible case
dp_factorial = [0] * (n+m+1)
dp_factorial[0] = 1

for i in range(1,n+m+1):
    dp_factorial[i] = dp_factorial[i-1] * i

total_num = dp_factorial[n+m] / (dp_factorial[m] * dp_factorial[n])

if k > total_num:
    print(-1)
else:
    return_string = ['z'] * (n+m)
    arr = list(range(n+m))
    nCr = list(itertools.combinations(arr, n))
    to_append = nCr[k-1]
    for index in to_append:
        return_string[index] = 'a'
    print(''.join(return_string))

 

<Solution - 정답>

따라서 다른 방식을 이용해야 합니다. 매번 a를 넣을지 z를 넣을지 결정을 해주는 방식을 사용합니다. 임의로 처음에 a가 온다고 가정하고, 이후에 남은 것들을 배열 하는 경우의 수가 찾아야 하는 k 보다 더 많다면, a가 아니라 z를 넣어주어야 하고 아닐시 a를 넣어주어야 합니다. 

실제 구현은 아래와 같습니다. 

import sys
import itertools

m, n, k = map(int,sys.stdin.readline().rstrip().split())

# calculate total posible case
dp_factorial = [0] * (n+m+1)
dp_factorial[0] = 1

for i in range(1,n+m+1):
    dp_factorial[i] = dp_factorial[i-1] * i

total_num = dp_factorial[n+m] / (dp_factorial[m] * dp_factorial[n])

if k > total_num:
    print(-1)
else:
    # find 
    return_string = ''
    left_a = m
    left_z = n
    while (len(return_string) != n+m):
        # case 1
        if k > (dp_factorial[left_a+left_z-1]/(dp_factorial[left_z]*dp_factorial[left_a-1])):
            return_string = return_string+'z'
            k -= (dp_factorial[left_a+left_z-1]/(dp_factorial[left_z]*dp_factorial[left_a-1]))
            left_z -= 1
        # case 2
        else:
            return_string = return_string+'a'
            left_a -= 1
    print(return_string)