[node.js] 카드 구매하기 ( 백준 11052번 )

const readline = require("readline");
const input = [];

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

rl.on("line", (line) => {
    input.push(line);
    if (input.length === 2) {
        main("0 " + line);
        rl.close();
    }
}).on("close", () => {
    process.exit();
});

/**
 *
 * @param {string} line
 */
const main = (line) => {
    const number = input[0];
    const prices = line.split(" ").map(Number);
    const DP = prices.map((el) => el);

    for (let i = 1; i <= number; i++) {
        for (let j = 1; j < prices.length; j++) {
            if (i - j > 0 && prices[j] + DP[i - j] > DP[i]) {
                DP[i] = prices[j] + DP[i - j];
            }
        }
    }

    console.log(DP[number]);
};

문제의 난이도는 사실 다른 DP와 비슷한데, 점화식을 생각하기가 조금 까다로웠다.
점화식을 생각할 때에는 항상 2개를 고려해야 한다.
맨 앞부터 생각하는 게 편한지, 뒤에서부터 생각하는 게 편한지.
2xn 타일링 문제는 뒤에서 생각하는 게 편했다. 하지만 얘는 앞에서부터 생각하는 게 편했다.
사실 어디서부터 생각하든 점화식의 모양은 n에 대한 점화식이라서 앞뒤 구분이 없긴 하다.