[BOJ] 2688 - 줄어들지 않아 (Python, JavaScript)

 

 

아이디어

 

동적 계획법으로 각 자릿수에서 줄어들지 않는 수의 개수를 구한다.

 

 

풀이 #1 (Python)

 

0으로 채운 65×10 크기의 2차원 리스트 dp를 생성한다.

dp[i][j]는 줄어들지 않는 i 자릿수 중 j로 시작하는 수의 개수이고, dp[i]의 합은 줄어들지 않는 i+1 자릿수의 개수다.

i 자릿수에서 0으로 시작하는 줄어들지 않는 수의 개수 dp[i][0]는 이전 자릿수에서 줄어들지 않는 수의 합 sum(dp[i-1])이고,

j로 시작하는 수의 다음 숫자 값은 j 이상이므로 dp[i][j]는 j-1로 시작하는 수를 제외한 dp[i][j-1]-dp[i-1][j-1]이다.

dp[65]까지 계산하면 이후 입력으로 주어지는 n 자릿수의 개수를 dp[n+1][0]으로 구할 수 있다.

 

import sys

input = sys.stdin.readline

def solution():
    dp = [[0]*10 for _ in range(65)]
    dp[0] = [1]*10
    for i in range(1, 65):
        dp[i][0] = sum(dp[i-1])
        for j in range(1, 10):
            dp[i][j] = dp[i][j-1]-dp[i-1][j-1]
    T = int(input())
    for t in range(T):
        n = int(input())
        print(dp[n][0])

solution()

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 마찬가지 방식으로 동작하며, dp[i-1]의 합을 구하기 위해 reduce 메서드를 이용한다.

 

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

let dp = Array.from(Array(65), () => Array(10).fill(0));
dp[0] = Array(10).fill(1);
for (let i=1; i<65; i++) {
    dp[i][0] = dp[i-1].reduce((acc, num) => acc+num, 0);
    for (let j=1; j<10; j++) dp[i][j] = dp[i][j-1]-dp[i-1][j-1];
}
const T = +input[0];
for (let t=1; t<=T; t++) {
    const n = +input[t];
    console.log(dp[n][0]);
}