문제 링크

성능 요약

메모리: 14188 KB, 시간: 112 ms

분류

조합론, 다이나믹 프로그래밍, 수학

제출 일자

2025년 2월 19일 02:49:25

문제 설명

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

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

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

입력

첫째 줄에 세 정수 N, M, K가 순서대로 주어진다.

출력

첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.

풀이

느낀점

• 1시간 반 가까이 고민해도 정말 모르겠어서 풀이를 봤는데도 이해하기 어려웠다.
• 설명을 이해하기 쉽게 잘 설명해 놓으신 글이 있어 도움이 많이 됐다.
• 이해하고 나니 쉬운데 이해를 하기까지 관점을 찾기가 정말 힘들었다.
• 거의 클론 코딩이라 풀었다는 의미는 없지만 좋은 풀이를 봤다는 점에서 의의를 둔다..

설계 : 120분

• a 문자 i개와 z 문자 j개를 가지고 조합할 수 있는 단어의 개수는 a 문자가 하나 부족한 단어 조합의 수와 z 문자가 하나 부족한 단어 조합의 수를 더한 것이다. 즉, dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 앞에서부터 문자를 고른다.
• a와 z중 문자를 고르는 방법은, a를 사용했다고 가정한 경우의 수 안에 k가 포함되는지 확인한다. 즉, k ≤ dp[aCnt-1][zCnt] 이면 a를 사용한다. 사전순이라는 조건 때문에 가능한 방법이다.
• z를 사용해야할 경우, k번째 단어 중 앞에서 a를 사용한 경우를 제외해야 한다. 즉, k -= dp[aCnt-1][zCnt]

코드(Java)

• 구현 시간: 30분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 사전_1256
 * Date: 2025.02.19
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		st = new StringTokenizer(br.readLine(), " ");
		int aCnt = Integer.parseInt(st.nextToken());
		int zCnt = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		// dp 테이블 초기화
		int[][] dp = new int[aCnt+1][zCnt+1];

		// 다른 문자가 하나도 없는 상태는 경우의 수가 모두 1
		for (int i = 1; i <= aCnt; i++) dp[i][0] = 1;
		for (int i = 1; i <= zCnt; i++) dp[0][i] = 1;

		// a가 하나 없는 경우의 수와, z가 하나 없는 경우의 수를 더함
		for (int i = 1; i <= aCnt; i++) {
			for (int j = 1; j <= zCnt; j++) {
				dp[i][j] = dp[i-1][j] + dp[i][j-1];
				if (dp[i][j] > 1_000_000_000) dp[i][j] = 1_000_000_000;
			}
		}

		// k가 만들 수 있는 단어의 개수보다 클 경우 -1 출력
		if (k > dp[aCnt][zCnt]) bw.write("-1");

		else {
			// 사용할 수 있는 문자가 아직 있다면 계속
			while (aCnt > 0 || zCnt > 0) {

				// a를 다 썼다면 끝까지 z사용 후 종료
				if (aCnt <= 0) {
					while (zCnt > 0) {
						bw.write("z");
						zCnt--;
					}
					break;

				// z를 다 썼다면 끝까지 a사용 후 종료
				} else if (zCnt <= 0) {
					while (aCnt > 0) {
						bw.write("a");
						aCnt--;
					}
					break;
				}

				// k가 이번 순서에 a를 사용한 경우의 수보다 작으면(그 안에 속하면) a 사용
				if (dp[aCnt-1][zCnt] >= k) {
					bw.write("a");
					aCnt--;

				// 아니라면 z사용 후 a를 사용한 경우의 수를 k에서 제거 (사전순이기 때문에)
				} else {
					bw.write("z");
					k -= dp[aCnt-1][zCnt];
					zCnt--;
				}
			}
		}

		bw.flush();
		bw.close();
		br.close();
	}
}