[BOJ] 13699 - 점화식 (Python, JavaScript)

 

 

아이디어

 

DP로 수열의 값을 구해 나간다.

 

 

풀이 #1 (Python)

 

def solution():
    n = int(input())
    t = [0]*(n+1)
    t[0] = 1
    for i in range(1, n+1):
        for j in range(i//2):
            t[i] += t[j]*t[i-j-1]
        t[i] *= 2
        if i%2:
            t[i] += t[i//2]**2
    print(t[-1])

solution()

 

 

 

풀이 #2 (JavaScript)

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function solution() {
    const n = Number(input[0]);
    let t = Array(n+1).fill(0n);
    t[0] = 1n;
    for (let i=1; i<=n; i++) {
        for (let j=0; j<parseInt(i/2); j++) {
            t[i] += t[j]*t[i-j-1];
        }
        t[i] *= 2n;
        if (i%2) t[i] += t[parseInt(i/2)]**2n;
    }
    console.log(String(t[n]));
}

solution();