[BOJ 1256] 사전 (풀이 미완성, DP사용 X)

서론

DP 태그가 떡하니 붙어있는데 DP 복습을 안하고 풀어서 DP로 풀 아이디어가 없었다. 

대신에 수학적인 개념을 이용해 풀어보았다. 설명이 잘 될진 모르겠다. 거지같은 코드에 괴상한 아이디어다.

 

2 2 x 케이스
a는 0으로, z는 1로 보기로 했다.
그래서 a와 z의 갯수를 충족하는 이진수를 작은 순부터 나열하기로 했다.

0011 // index = 0
0101
0110
1001
1010
1100 // index = 5

처음 나오는 1의 위치를 x라고 두면, 기준으로 0을 배열할 수 있는 경우의 수가 2C0이다.
0<= K-1 < 2C0을 만족할 때, 단어 기준 맨 오른쪽 char부터 0으로 메겼을 때, 0, 1번째 자릿수에 1을 넣는다.

4번(문제에서는 5로 주어지는 K, 단어는 1010, 즉 zaza)의 문자열을 찾고자 할 때는, 다음과 같은 절차를 거친다.
2C0 <= K-1 < 2C0 + 3C1 (만족하지 않음)
2C0 + 3C1 <= K-1 < 2C0 + 3C1 + 4C2 (만족)
=> 파스칼의 삼각형에서 하키스틱의 법칙을 이용해 좀 더 간략하게 쓸 수 있다.

4C1 <= K-1 < 5C2
오른쪽에서 (4-1)번째의 문자가 z가 된다.
나머지 z를 더 찾아야 하기 때문에, 

(K-1) - 4C1을 재귀함수 호출 시 K로 전달한다.
k = 0, n=2, m=1 (z 1개의 위치는 이미 확정지었으므로)을 구하는데, 위와 같은 방법으로 반복수행하면 z의 위치를 모두 구할 수 있으며, a로 가득찬 String의 오른쪽으로 부터 인덱스를 통해 접근하여 z로 변경하면 우리가 원하는 단어를 구할 수 있다.

코드

설명도 못하겠고 코드는 더욱더 비참하다.

import java.io.*;
import java.util.*;
public class Main {
	
	static StringBuilder sb = new StringBuilder();
	static int N; // a
	static int M; // z
	static int K; // target
	
	static PriorityQueue<Integer> pq = new PriorityQueue<>();
	static String s;

	static void find(int n, int k, long prevComb, long target, int bound) {
		long currComb = 0; 
		if(k == 0) {
			prevComb = 0;
			currComb = 1;
		}
		else {
			currComb = (prevComb/k)*(n);
		}
		int i = 0;
		for(i = n; i <= bound; i++, k++) {			
			if(prevComb <= target && currComb > target) {
				if(prevComb == 0) {
					for(int j = i-1; j >= 0; j--) {
						pq.offer(j);
					}
					break;
				}
				find(i-k-1, 0, 0, -prevComb+target, i-1);
				pq.offer(i-1);
				break;
			}
			prevComb = currComb;
			currComb = (prevComb*(i+1)/(k+1)); 
		}
		if(i == M+N+1) {
			System.out.println("-1");
			System.exit(0);
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		char[] chars = new char[N+M];
		Arrays.fill(chars, 'a');
		if(K == 1) {
			for(int x = 0; x < M; x++) {
				chars[N+M-1-x] = 'z';
			}
		}
		else {				
			find(M+1, 1, 1, K-1, N+M);
		}
		while(!pq.isEmpty()) {
			chars[N+M-1-pq.poll()] = 'z';
		}
		s = new String(chars);
		bw.write(s);
		bw.flush();
		bw.close();
		
		pq.clear();
	}
}

문제의 의의?

DP로 푸는게 정석인 문제에 남들이 해보지 않은 수학적 접근으로 독창적으로 풀었지만, DP 공부엔 도움이 안되고 시간만 많이 잡아먹었다. 인터넷에 해당 문제의 많은 풀이가 있지만 비슷한 풀이는 보지 못했습니다. 만약 유사하거나 같은 풀이를 발견하신다면 감사하겠습니다.

 

질문 안 받습니다.