흙금이네 블로그

아이디어 동적 계획법으로 남은 a와 z의 개수에 따른 조합의 수를 구한 후, 이분 탐색의 원리로 문자열을 찾아 나간다. 풀이 행은 a의 남은 개수, 열은 z의 남은 개수를 의미하는 (N+1)*(M+1) 크기의 2차원 리스트 dp를 만든다. 한 문자가 0개 남았을 때는 다른 문자 개수와 상관없이 모두 다른 문자로 채워지는 한 가지 경우이므로 1로 초기화한다. 두 문자 모두 0개 남은 dp[0][0]은 경우의 수로는 0이 맞으나 이후 코드에서 발생하는 예외를 위해 1로 채운다. K가 주어진 문자 a와 z로 조합할 수 있는 단어 수의 범위를 넘어서면 -1을 출력한다. 그렇지 않으면 i는 N-1, j는 M부터 두 값이 모두 0 이상일 동안 while문을 반복하며 결과값 res를 채워 나간다. a는 z보다 사전순..