[백준 1256] 사전 / 자바 / 조합

#문제         

레벨: G2
알고리즘: 조합, dp
풀이시간: 1시간
힌트 참조 유무: 유

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

 

---

#문제 풀이        

이 문제에서 얻어갈 점은 두가지입니다.

1. 조합을 계산하는 방법(일반 계산, dp로 표현)
2. 문제 해결 아이디어

문제 해결 아이디어부터 설명드리겠습니다. 

문제를 보자마자 모든 알파벳 조합을 만들어 보는 것은 시간제한이 걸린다는 것을 직감할 수 있습니다. 그렇다면 저희가 해야 할 일은 앞에 놓을 수 있는 글자들을 놓아보는 것입니다. 앞에 a가 올려면 a~~~~에 문자열이 K번 째 문자열이 포함된다는 거고 앞에 z가 올려면 z~~~~에 k 번째 문자열이 포함된다는 겁니다.

다르게 설명드리면, a~~~~에 놓을 수 있는 경우의 수가 K 보다 작다면, z를 놓아야 한다는 겁니다. 
z를 놓았으니, k = k- (a~~~~~의 경우의수) 를 해줍니다.
다시 za~~~~~에 놓을 수 경우의 수가 K 보다 작다면, z를 놓아야 한다는 것이고, k가 더 작다면  za~~~~~~ 에 포함되는 것이기 때문에, za로 픽스합니다 이과정을 반복하면서 하나씩 놓아보는 것입니다.

그렇다면, a~~~~~의 경우의 수는 어떻게 구해야 할까요? ~~~~가 5자리이고 남은 글자수가 a = 3, z =2 이면 5C2입니다. 남은 자리에서 z를 놓을 경우의 수이기 때문입니다. 

경우의 수를 구하는 방법은 2가지입니다.

일반계산: O(r)

long nCr(int n, int r) {
    long result = 1;
    for(int i = 1; i <= r; i++) {
        result *= (n - i + 1);
        result /= i;
    }
    return result;
}

 

dp: O(n*r)

n C r      =     n-1 C  r-1     +    n-1 C r 이니 아래와 같이 코드를 짤 수 있습니다. 파스칼을 dp로 구현하는 것 같이 중복 계산을 피하기 위해 dp로 구현합니다.

long nCr(int n, int r) {
        if(r == 0 || r == n) return 1;
        if(dp[n][r] != 0) return dp[n][r];
        
        return dp[n][r] = Math.min(combination(n-1, r-1) + combination(n-1, r), 1000000001);
    }

 

n C r을 dp 로 구현하면 좋은점이 한 번  dp 배열을 채우면 a~~~~ 경우의 수를 구할 때 시간복잡도 O(1)로 값을 구할 수 있습니다. nCr을 일반 계산으로 구하게 된다면, dp보다 구하는 시간복잡도가 빠르지만 매번 O(r)이 걸린다는 점이 단점입니다. 이것을 고려하여 nCr을 구현하면 좋을 것 같습니다. 

저는 두가지 방식으로 풀어봤는데 메모리, 시간 상 거의 차이가 없었습니다.

 

---

#풀이 코드      

일반계산 ver

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

public class Main {
    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());
        
        int N = Integer.parseInt(st.nextToken()); // a의 개수
        int M = Integer.parseInt(st.nextToken()); // z의 개수
        double K = Double.parseDouble(st.nextToken());
        
        if(combination(N + M, M) < K) {
            System.out.println(-1);
            return;
        }
        
        findKth(N, M, K);
        System.out.println(sb.toString());
    }
    
    static double combination(int n, int r) {
        if(r > n/2) r = n-r; // 더 작은 r 선택
        
        double result = 1.0;
        for(int i = 1; i <= r; i++) {
            result *= (n - i + 1);
            result /= i;
            if(result > 1000000001) return 1000000001; // 최대값 제한
        }
        return result;
    }
    
    static void findKth(int a, int z, double k) {
        if(a == 0) {
            for(int i = 0; i < z; i++) sb.append('z');
            return;
        }
        if(z == 0) {
            for(int i = 0; i < a; i++) sb.append('a');
            return;
        }
        
        double leftCount = combination(a + z - 1, z);
        if(k <= leftCount) {
            sb.append('a');
            findKth(a-1, z, k);
        } else {
            sb.append('z');
            findKth(a, z-1, k-leftCount);
        }
    }
}

 

dp ver

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

public class Main {
    static double[][] dp;
    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());
        
        int N = Integer.parseInt(st.nextToken()); // a의 개수
        int M = Integer.parseInt(st.nextToken()); // z의 개수
        double K = Double.parseDouble(st.nextToken());
        
        dp = new double[N+M+1][M+1];  // nCr을 담을 배열
        
        if(combination(N+M, M) < K) {
            System.out.println(-1);
            return;
        }
        
        findKth(N, M, K);
        System.out.println(sb.toString());
    }
    
    static double combination(int n, int r) {
        if(r == 0 || r == n) return 1;
        if(dp[n][r] != 0) return dp[n][r];
        
        return dp[n][r] = Math.min(combination(n-1, r-1) + combination(n-1, r), 1000000001);
    }
    
    static void findKth(int a, int z, double k) {
        if(a == 0) {
            for(int i = 0; i < z; i++) sb.append('z');
            return;
        }
        if(z == 0) {
            for(int i = 0; i < a; i++) sb.append('a');
            return;
        }
        
        double leftCount = combination(a+z-1, z);
        if(k <= leftCount) {
            sb.append('a');
            findKth(a-1, z, k);
        } else {
            sb.append('z');
            findKth(a, z-1, k-leftCount);
        }
    }
}