[백준 1256] 사전 (DP, 자바스크립트)

Jiyoung Park·2023년 1월 20일
0

Dynamic Programming

목록 보기
5/8

사전

문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.

규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.

N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

입력
첫째 줄에 세 정수 N, M, K가 순서대로 주어진다.

출력
첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.

제한

  • 1 ≤ N, M ≤ 100
  • 1 ≤ K ≤ 1,000,000,000

풀이

a가 앞에 올수록 앞순서, z가 앞에 올수록 뒷순서가 된다.
그러므로 앞에 a가 오는 경우와 z가 오는 경우를 나누어 생각하면, 사전순으로 정렬이 된다.

예를 들어, a가 2개이고 z가 2개인 경우는 아래 그림과 같다.

앞에 a가 오는 경우와 z가 오는 경우의 조합의 수를 계산하여 k번째 문자열이 오는 위치를 찾는다.
(이 때 조합의 수는 nCr로 구한다.)

a와 z로만 이루어진 문자열이 되면 이전 호출로 되돌아가며 앞에 a 혹은 z를 붙여준다.

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [n, m, k] = require("fs").readFileSync(filePath).toString().trim().split(" ").map(Number);

function combination(n, r) { // nCr
    let result = 1;
    for (let i=n; i>n-r; i--) result *= i;
    for (let i=1; i<=r; i++) result /= i;
    return result;
}

function divide(a, z, k) { // a의 개수, z의 개수, k번째 문자열
    if (a === 0 || z === 0) {   // a만 남거나 z만 남으면 만들 수 있는 문자열은 1가지
        let answer = "";
        for (let i=0; i<a; i++) answer += "a";
        for (let i=0; i<z; i++) answer += "z";
        return answer;
    }

    let cnt = combination(a+z-1, Math.min(a-1, z)); // a가 앞에 올 때 만들 수 있는 조합의 개수
    if (k <= cnt) return "a" + divide(a-1, z, k);   // cnt가 k보다 크면, 앞에 a를 두고 나머지 알파벳을 조합했을 때 k번째 문자열을 구할 수 있음
    else return "z" + divide(a, z-1, k-cnt);        // cnt가 k보다 작으면, 앞에 z를 두고 나머지를 조합. 이 때 k는 앞에 오는(a로 시작하는) cnt개의 문자열보다 뒤에 있기 때문에 k-cnt로 renumbering됨
}

if (combination(n+m, Math.min(n, m)) < k) console.log("-1"); // a n개와 z m개로 만들 수 있는 문자열이 k개보다 적으면 -1 출력
else console.log(divide(n, m, k));

0개의 댓글