알고리즘/알고리즘 문제풀이

Do it! 알고리즘 코딩 테스트(82번)

lusida0131 2022. 6. 30. 15:14
728x90

82번 사전


내가 떠올린 풀이 해설

a와 z의 개수가 각각 N, M개일 때 이 문자들로 만들 수 있는 모든 경우의 수는 N + M 개에서 N개를 뽑는 경우의 수 또는 N + M개에서 M개를 뽑는 경우의 수와 동일하다. arr배열을 초기화하고, 점화식으로 값을 계산해 저장한다. 몇 번째 문자열을 표현해야 하는지를 나타내는 변수를 K라고 하자 현재 자릿수에서 a를 선택했을 때 남아 있는 문자들로 만들 수 있는 모든 경우의 수는 T이다. T와 K를 비교해 문자를 선택한다. 문자 선택 기준은 T >= K : 현재 자리 문자를 a로 선택 T < K : 현재 자리 문자를 Z로 선택하고, K = K - T로 업데이트 

ex) a = 2, z = 2이고 a를 선택했을 때 나머지 문자열로 만들 수 있는 경우의 수는 arr[남은문자 총 개수 : 3][남은 z개수 : 2]

arr [3][2] = 3 >= k(2)이므로 a 확정 -> z는 2개 남음

arr [3][2] = 3 < k(2)이므로 z 확정 -> z는 1개 남음 -> K = K - T = 1로 업데이트

arr [1][1] = 1 >= k(1)이므로 a 확정 -> z는 1개 남음

arr [0][1] = 1 < k(2)이므로 z 확정


정확한 풀이

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

public class Baek1256 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int [][] arr = new int[202][202];
		for(int i = 0; i <= 200; i++) {  // 조합 테이블 초기화 
			for(int j = 0; j <= i; j++) {
				if(j == 0 || j == i) {
					arr[i][j] = 1;
				}
				else {
					arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
					if(arr[i][j] > 1000000000) { //k 범위가 넘어가면 범위의 최댓값 
						arr[i][j] = 1000000001;
					}
				}
			}
		}
		if(arr[n + m][m] < k) { // 주어진 자릿수로 만들 수 없는 K번째 수이면 
			System.out.println(-1);
		}
		else {
			// a를 선택했을 때 남은 문자로 만들 수 있는 모든 경우의 수가 K 보다 크면 
			while(!(n == 0 && m == 0)) {
				if(arr[n - 1 + m][m] >= k) {
					System.out.print("a");
					n--;
				}
				else { // 모든 경우의 수가 k보다 작으면 
					System.out.print("z");
					k = k - arr[n - 1 + m][m]; // k값 업데이트 
					m--;
				}
			}
		}
	}
}

오늘의 회고

오늘은 캐치 콘에서 하는 세미나 참가로 조합 문제 1문제를 풀었습니다. 이제 조합 문제 1문제가 남았고 이제 DP를 들어갈 차례입니다. DP까지 풀면 중요한 알고리즘은 다 풀었습니다. 개념 복습을 하면서 다시 문제 풀고 문제 복습을 하는 순서로 공부를 해야겠습니다.

728x90