[BOJ] 10978 - 기숙사 재배정 (Python, JavaScript)

 

 

아이디어

 

DP로 완전순열을 구한다.

 

 

풀이 #1 (Python)

 

점화식을 구하기 위해 임의로 학생과 기숙사에 번호를 매기고, 1번 학생이 K번 기숙사에 배정되는 경우를 고려한다.

K번 학생이 1번 기숙사에 배정되는 경우의 수는 1번 학생과 K번 학생을 제외하고 학생 수가 N-2인 경우의 수와 같다.

K번 학생이 1번 기숙사에 배정되지 않는 경우의 수는 1번 학생을 제외하고 학생 수가 N-1인 경우의 수와 같다.

K는 1을 제외한 N-1개의 수가 가능하므로 두 경우의 수를 더하여 N-1만큼 곱하면 학생 수가 N인 경우의 수를 구할 수 있다.

 

import sys

input = sys.stdin.readline

def solution():
    T = int(input())
    dp = [0]*21
    dp[2] = 1
    for i in range(3, 21):
        dp[i] = (dp[i-1]+dp[i-2])*(i-1)
    for _ in range(T):
        N = int(input())
        print(dp[N])

solution()

 

 

 

풀이 #2 (JavaScript)

 

readline 모듈을 사용해 입력 받는다.

 

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];

rl.on('line', (line) => {
    input.push(line);
}).on('close', () => {
    solution();
    process.exit();
});

function solution() {
    const T = Number(input[0]);
    let dp = Array(21).fill(BigInt(0));
    dp[2] = BigInt(1);
    for (let i=3; i<21; i++) {
        dp[i] = (dp[i-1]+dp[i-2])*BigInt(i-1);
    }
    for (let t=1; t<=T; t++) {
        N = Number(input[t]);
        console.log(String(dp[N]));
    }
}

solution();

 

 

이 문제에서 fs 모듈을 사용하면 런타임 에러가 발생한다.

// 런타임 에러 (EACCES) 발생 코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
...