사전(백준_1256)

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

1256번: 사전

 

문제 설명

이번 문제는 사전에 a와 z로만 이루어진 문자열들이 알파벳 순서대로 수록되어 있다. 이 때 n과 m이 주어졌을 때, 자신의 사전에 k번째 문자열을 출력하는 것이다.

예를 들어 n=2, m=2 이면 a가 2개, z가 2개 이고 2번째 문자열이므로 azaz이다.

 

문제에 대한 아이디어

문자열의 순서를 찾으라는 것에서 순열이 생각났다. 예시 처럼 a a z z가 주어졌을 때, 고등학교 때 배운 4! / 2! * 2! 이 생각 났다. 

이 문제는 조합과 함께 DP를 사용하여 순서대로 만들어가면 된다.

 

조합 2차원 배열 만들기

조합의 경우의 수를 모두 저장해 놓는 2차원 배열을 만들면 된다. 간단하게 숫자가 4개 있을 때를 생각해보겠다.

행의 index가 몇개의 수라는 뜻이고 열의 index가 몇개의 수 중 몇개를 선택한다라는 뜻이다. 즉 3,2인 곳은 3 C 2라는 뜻이다.

i 는 행, j는 열 이라고 하자!!

• j == 0,  i == j 이면 1 이다.
• D[ i ][ j ] = D[ i - 1 ][ j - 1 ] + D[ i - 1 ][ j ] 이다. 왜냐하면 4 C 3은 4개중에 3개를 선택했다는 뜻인데 이것은 3개중에 2개를 선택하고 4번째에 선택하는 경우와 3번째까지 3개를 선택하고 4번째에 선택하지 않은 경우의 합이기 때문이다. 

int arr[][] = new int [201][201];
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] + arr[i-1][j-1];
            if(arr[i][j] > 1000000000) arr[i][j] = 1000000001;
        }
    }
}

 

문자 선택하기

예를 들어서 설명하면,  전체 수는 4개가 있다고 가정한다. (a a z z)

• 제일 처음 a를 선택하면 만들 수 있는 경우는 a z z로 만들 수 있는 경우의 수이다. 3개중에 2개를 선택할 경우의 수이므로 3이다. k 가 3보다 작으면 a를 선택한다. n 하나 줄인다.
• 만약 k가 3보다 크다면 z를 선택해야한다. 그리고 k를 경우의 수만큼 빼야 하므로 k = k - arr[n+m-1][m] 을 해줘야 한다. 그 후 m을 하나 줄인다.

if(arr[n+m][m] < k){
    System.out.println(-1);
} else{
    while(!(n == 0 && m == 0)){
        if(k <= arr[n+m-1][m]){
            System.out.print("a");
            n--;
        }else{
            System.out.print("z");
            k = k - arr[n+m-1][m];
            m--;
        }
    }
}

 

전체 코드

import java.util.Scanner;

public class Main {
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long k = sc.nextLong();
        int arr[][] = new int [201][201];
        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] + arr[i-1][j-1];
                    if(arr[i][j] > 1000000000) arr[i][j] = 1000000001;
                }
            }
        }
        if(arr[n+m][m] < k){
            System.out.println(-1);
        } else{
            while(!(n == 0 && m == 0)){
                if(k <= arr[n+m-1][m]){
                    System.out.print("a");
                    n--;
                }else{
                    System.out.print("z");
                    k = k - arr[n+m-1][m];
                    m--;
                }
            }
        }

    }
}

https://github.com/Heron-Woong/CodingTest_Practice/commit/e6443d435f7a36aaf028a49926363f0c0146563f

백준_1256, 사전 · Heron-Woong/CodingTest_Practice@e6443d4