[코테] 백준 1256번 : 사전 (java)

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

알고리즘 분류 : 수학, 다이나믹 프로그래밍, 조합론

❓문제

---

🔅해석

'a'와 'z'의 조합으로 n번째 단어를 출력하는 문제이다.

사전에는 알파벳 순서대로 수록되어 있으므로 'a'로 시작하는 문자의 조합으로 계산해본다.

입력 : 2 2 6

 

1. a_ _ _ 

'a'로 시작하는 문자의 조합 개수는 남은 3자리수와 남은 'z'의 갯수 3C2이다.

조합 표

 

3C2 = 3이므로 'a'로 시작했을 때 3가지의 조합을 만들 수 있다.

우리는 6번째(K) 순서를 원하므로 'z'로 시작한다는 것을 알 수 있다. (3C2 < K)

1) 결과값을 담는 sb에 'z'를 추가하고

2) 'z' 카운트를 하나 감소시킨다.

3) K의 값을 조합 수 만큼 감소시킨다.

 

2. z a _ _

위에서 'z'로 시작하는 것을 알고 다음으로 'a'를 임의로 붙여본다.

그럼 남은 자릿수와 남은 'z'의 갯수로 2C1 = 2이다.

현재 K는 (6-3) 이므로 2C1 < K가 되어 1번과 같이 3가지 순서를 진행한다.

 

3. z a z _

조합을 돌려보지 않아도 이미 'z'개수는 0이 되어 나머지 자리는 'a'로 채워진다는 것을 알 수 있다.

 

 

조합 생성 메소드

public static int combination(int n, int r) {
    if (n == r || r == 0) {
        return 1;
    } else if (dp[n][r] != 0) {
        return dp[n][r];
    } else {
        return dp[n][r] = Math.min((int) 1e9, combination(n - 1, r - 1) + combination(n - 1, r));
    }
}

 

선택사항)

Math.min((int) 1e9, ...): 

계산된 조합 값이 10^9 (즉, 1,000,000,000)보다 큰 경우, 상한을 적용하여 최대값을 10^9로 제한한다.
조합의 수가 매우 커질 수 있기 때문에, 특정 문제에서 오버플로우를 방지하기 위해 위 같은 제한을 둔다.

---

⭕정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N, M, K;
	static int[][] dp = new int[201][201];
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		StringBuilder sb = new StringBuilder();

		if (K > combination(N + M, M)) {
			sb.append(-1);
		} else {
			int n = N, m = M, k = K;

			for (int i = 0; i < N + M; i++) {
				if (n == 0) {
					sb.append("z");
				} else if (m == 0) {
					sb.append("a");
				} else {
					int aCount = combination(n + m - 1, m);
					if (aCount >= k) {
						// a로 시작
						sb.append("a");
						n--;
					} else {
						// z로 시작
						sb.append("z");
						m--;
						k -= aCount;
					}
				}

			}
		}
		System.out.println(sb.toString());
		br.close();
	}

	public static int combination(int n, int r) {
		if (n == r || r == 0) {
			return 1;
		} else if (dp[n][r] != 0) {
			return dp[n][r];
		} else {
			//
			return dp[n][r] = Math.min((int) 1e9, combination(n - 1, r - 1) + combination(n - 1, r));
		}
	}
}

 

---

❗결과