백준 1256번 사전

문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.

규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.

N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘: DP

 N개의 a와 M개의 z로 이루어진 단어 중 사전순으로 K번째 단어를 출력하는 문제였습니다.

(1) 코드 8~9

 'dp[x][y] : x개의 a, y개의 z 로 단어를 만드는 경우의 수' 로 dp값을 설정했습니다.

(2) 코드 10~20

 x개의 a, y개의 z 로 단어를 만드는 경우는
 1. x-1개의 a, y개의 z 로 만든 단어 앞에 a를 붙이는 경우
 2. x개의 a, y-1 개의 z 로 만든 단어 뒤에 z를 붙이는 경우 입니다.
 따라서 dp[x][y] = dp[x-1][y] + dp[x][y-1] 라는 점화식을 유도할 수 있습니다.
 이를 이용해 dp값을 계산해주는 함수를 만들어 줍니다.

(3) 코드 21~44

 정답단어를 만드는 함수를 만들어 줍니다.
 총 N+M 크기의 단어를 만들어야 합니다.
 맨 앞부터 a를 붙여야 하는지 z 를 붙여야 하는지 판단하면서 단어를 만들어줍니다.