[백준/JAVA] 1256번: 사전

🔺 문제

1256번: 사전

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, K;
    static int[][] D;
    static int MAX = 1000000000;
    
    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());   // "a" 개수
        M = Integer.parseInt(st.nextToken());   // "z" 개수
        K = Integer.parseInt(st.nextToken());
        
        // DP 배열 채우기
        D = new int[202][202];
        for(int i = 0 ; i <= 200 ; i++) {
            for(int j = 0 ; j <= i ; j++) {
                if(j == 0 || j == i) {
                    D[i][j] = 1;
                }
                else {
                    D[i][j] = D[i - 1][j] + D[i - 1][j - 1];
                    if(D[i][j] > MAX) D[i][j] = MAX + 1;
                }
            }
        }
        
        // 불가능한 K인 경우 (= 사전에 수록된 문자열 개수 < K인 경우)
        if(D[N + M][M] < K) {
            System.out.println("-1");
        }
        else {
            // 모든 문자를 사용할 때까지
            while(!(N == 0 && M == 0)) {
                int T = D[N - 1 + M][M];    // a를 선택하고 남은 문자로 만들 수 있는 모든 경우의 수
                   
                if(T >= K) {    //  a 선택하고 남은 문자로 만들 수 있는 모든 경우의 수가 K보다 크면
                    System.out.print("a");    // 현재 자리 문자를 a로 선택
                    N--;
                }
                else {  // 모든 경우의 수가 K보다 작으면
                    System.out.print("z");    // 현재 자리 문자를 z로 선택
                    K -= T;   // K를 계산된 모든 경우의 수를 뺀 값으로 저장
                    M--;
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ 조합 & DP

 

💥 유의사항

• 두 문자로만 구성되어 있을 때, 이 문자들로 만들 수 있는 모든 경우의 수
 = N + M 개에서 N/M개를 뽑는 경우의 수 (조합)

 

• 조합 점화식

D[ i ][ j ] = D[ i - 1 ][ j ] + D[ i  - 1 ][ j - 1]

 

• 문자 선택 기준

(T : 현재 자릿수에서 a를 선택하고 남은 문자들로 만들 수 있는 모든 경우의 수)

⇨ T ≥ K : 현재 자리 문자를 a로 선택

⇨ T < K : 현재 자리 문자를 z로 선택 & K -= T로 업데이트

 

---

🔺 다른 풀이들

- 주석 설명 짱...

[백준 1256] 사전(Java)

[백준 1256] 사전 (JAVA)

 

 

- 자세한 풀이 설명... 최고ㅠㅠ

[백준 알고리즘]1256번: 사전_Java

[알고리즘] - 백준 1256번 : 사전(JAVA)

---

💬 느낀 점

나에게는 너무 이해가 안 가는 조합....

사람이 이래서 수학을 잘하고 봐야하는 것 같다...고 느낌

으아악

az,,, 아재버거....

 

1회독	2회독	3회독	4회독	5회독
V	7/3

 

 

(+ 7/4 2회독)

[백준 알고리즘]1256번: 사전_Java

위 블로그 참고.........

복습을 50만번 해야할 거 같다...ㅋ

import java.util.*;
import java.io.*;
 
public class Main {
    static double[][] dp = new double[101][101];
    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 = Integer.parseInt(st.nextToken());   // K번쨰 문자열 구하기
        
        if(check(N, M) < K) {
            System.out.println(-1);
        }
        else {
            getResult(N, M, K);
            System.out.println(sb.toString());
        }
        
    }
    
    // 개수 구하는 함수 (dp배열 채움)
    private static double check(int a, int z) {
        if(a == 0 || z == 0)    return 1;
        if(dp[a][z] != 0)       return dp[a][z];
        
        return dp[a][z] = Double.min(check(a-1, z) + check(a, z-1), 1000000001);
    }
    
    // 문자열 만드는 함수
    private static void getResult(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 check = check(a-1, z);
        if(k > check) {
            sb.append("z");
            getResult(a, z-1, k-check);
        }
        else {
            sb.append("a");
            getResult(a-1, z, k);
        }
    }
}
 

 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편