[백준, Java] 1256번, 사전, (조합, 다이나믹 프로그래밍)

 

문제 링크

1256번: 사전

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 'a', 'z'만 이용한 사전을 만들어야 합니다.

2. 'a'는 N개, 'z'는 M개가 존재합니다.

3. K번째 사전에 있는 문자열을 결과로 출력합니다.

4. K번째 문자열이 사전에 존재하지 않으면 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 이항계수를 통해 조합의 개수를 기준으로 K번째 문자열을 탐색합니다.

 

3. 탐색을 통해 얻은 문자열을 결과로 출력합니다.

 

이항계수(조합)

 

이항계수 : 주어진 크기의 (순서 없는) 조합의 가짓수

 

nCm : 형태의 조합을 뜻합니다.

 

점화식 : n! ÷ (m! × (n-m)!)

 

또한, 이항계수 피라미드를 통해서도 구할 수 있습니다.

 

 

DP[i][j]

 

i : nCm의 n

 

j : nCm의 m

 

DP[i][0] = 1 : nC0은 항상 1입니다.

 

DP[i][i] = 1 : nCn은 항상 1입니다.

 

점화식으로 표현하면

 

i > 0 && j < m

 

DP[i][j] = DP[i-1][j-1] + DP[i-1][j] ;

 

 

이와 같이 조합에 대한 값을 이항계수로 구할 수 있습니다.

 

K번째 문자열 구하기

 

사전은 오름차순으로 정렬되기 때문에 문자열은 'a'부터 시작합니다.

 

K번째 문자열을 만들 때에는 2가지로 나누어집니다.

 

 

1. 'a'의 문자열을 사용한다.

 

2. 'z'의 문자열을 사용한다.

 

'a'을 사용한다는 것?

 

→ 현재 'a'가 왔을 때 조합으로 K번째 문자열을 만들 수 있습니다.

 

n+m-1Cm ≥ K : 'a', 'z'에서 'z'를 m개 썼을 때 만들 수 있는 조합의 개수가 K보다 크거나 같을 때

 

'z'을 사용한다는 것?

 

→ 현재 'a'가 왔을 때 조합으로 K번째 문자열을 만들 수 없어서, 'a'가 최전방에 왔을 때 조합 이후에 K번째 문자열이 나온다.

 

n+m-1Cm < K : 'a', 'z'에서 'z'를 m개 썼을 때 만들 수 있는 조합의 개수가 K보다 작을 때

 

K = K - n+m-1Cm

 

 

aaaazzz일 때

 

zaaaazz가 되려면

 

a|aaazzz|의 조합의 개수가 모두 탐색되어야 하기 때문에 'a'가 맨 앞에 왔을 대 조합을 빼주어야 한다는 것입니다.

 

※ -1을 진행하는 이유는 'a'을 사용했다고 가정하기 때문입니다.

 

 

마지막으로 n+mCm < K 을 만족한다면?

 

→ 'a'와'z'을 모두 사용한 조합의 개수가 K보다 작기 때문에 K번째 문자열이 존재하지 않는다고 판단할 수 있습니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 2

 

M : 2

 

K : 2

 

2. 이항계수를 통해 조합의 개수를 기준으로 K번째 문자열을 탐색합니다.

 

이항계수

 

 

 

 

 

문자열을 만드는 2가지 경우로 탐색 진행.

 

a의 개수 : 2개

 

z의 개수 : 2개

 

n+m-1Cm = ₃C₂ = 3

 

₃C₂(3) ≥ K(2)을 만족 → 'a' 사용!

 

 

 

a의 개수 : 1개

 

z의 개수 : 2개

 

n+m-1Cm = ₂C₂ = 1

 

₂C₂(1) ＜ K(2)을 만족 → 'z' 사용

 

'z'을 사용하였기 때문에 aa|zz|의 조합의 개수를 K에서 빼줍니다.

 

K = K(2) - ₂C₂ (1) = 1

 

 

a의 개수 : 1개

 

z의 개수 : 1개

 

n+m-1Cm = ₁C₁ = 1

 

₁C₁(1) ＜ K(1)을 만족 → 'a' 사용

 

 

a의 개수 : 0개

 

z의 개수 : 1개

 

n+m-1Cm = oC₁ = 0

 

oC₁(0) ＜ K(1)을 만족 → 'z' 사용

 

'z'을 사용하였기 때문에 aza|z|의 조합의 개수를 K에서 빼줍니다.

 

K = K(1) - oC₁(0) = 1

 

 

모든 'a'와 'z'을 사용하였습니다.

 

 

3. 탐색을 통해 얻은 문자열을 결과로 출력합니다.

 

탐색을 통해 얻은 문자열 : azaz

 

 

azaz 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 사전의 정보를 띄어쓰기 기준 나누었습니다.
• 이항계수 점화식으로 DP[][]배열에 조합의 정보를 저장합니다.
• 'a', 'z'을 모두 사용해도 K번째 문자열을 만들지 못하면 -1을 결과값으로 만듭니다.
• 조합을 기준으로 'a', 'z'을 사용하는 2가지 경우를 통해 K번째 문자열을 탐색합니다.
• 탐색한 K번째 문자열을 Bufferedwriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        StringBuilder result = new StringBuilder();
        long[][] DP = new long[N+M+1][N+M+1];
        //이항계수 조합 값 저장
        DP[0][0] = 1;
        for(int i=1;i<=N+M;i++){
            DP[i][0] = 1;
            DP[i][i] = 1;
            for(int j=1;j<i;j++){
                DP[i][j] = DP[i-1][j-1] + DP[i-1][j];
                //long 범위를 벗어날 수 있기 때문입니다.
                if(DP[i][j] > 1000000000){
                    DP[i][j] = 1000000001;
                }
            }
        }

        //K번째 문자열을 만들 수 없을 경우
        if(DP[N+M][N] < K){
            bw.write("-1");
        }else{
            //문자열 만들기 진행
            while (N != 0 || M != 0) {
                //'a'을 사용하는 경우
                if (DP[N + M - 1][M] >= K) {
                    result.append("a");
                    N--;
                } else {		//'z'을 사용하는 경우
                    result.append("z");
                    K -= DP[N + M - 1][M];
                    M--;
                }
            }
        }
        //K번에 대한 문자열의 값 BufferedWriter 저장
        bw.write(result.toString());
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}