[JavaScript/DP] 백준 골드 5 : 2240 - 자두나무

https://www.acmicpc.net/problem/2240

2240번: 자두나무

---

📌 작성한 코드 

// 2240
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [T, W] = input.shift().split(" ").map(Number);
const pos = input.map(Number);

const dp = Array.from({ length: T + 1 }, () => new Array(W + 1).fill(0));

if (pos[0] === 1) {
    dp[1][0] = 1;
    dp[1][1] = 0;
} else {
    dp[1][0] = 0;
    dp[1][1] = 1;
}

for (let i = 2; i <= T; i++) {
    for (let j = 0; j <= W; j++) {
        let isCorrectPosition = 0;

        if (j % 2 === 0 && pos[i - 1] === 1) {
            isCorrectPosition = 1;
        }
        if (j % 2 === 1 && pos[i - 1] === 2) {
            isCorrectPosition = 1;
        }

        if (j === 0) dp[i][j] = dp[i - 1][j] + isCorrectPosition;
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + isCorrectPosition;
    }
}

console.log(Math.max(...dp[T]));

📌 설명 

자두가 받을 수 있는 자두의 최대 개수를 구하는 문제이다.

dp를 이용해서 매 초마다, 이동한 횟수에 따라 얻을 수 있는 자두의 개수를 구하며 최종적인 최대 개수를 구할 것이다.

 

점화식 

dp[i][j] : i초에 j번 이동했을 때 얻을 수 있는 자두의 최대 개수 

- 위치 1에서 시작하기 때문에 이동 횟수가 짝수면 1번에서 자두가 떨어질 것이고, 이동 횟수가 홀수면 2번에서 자두가 떨어질 것이다.

- 이동횟수가 0이면 가능한 방법이 j가 0인 경우밖에 안되므로 [i-1][0]  + (현재 위치에 따라 받을 수 있는 자두)

- 이동횟수가 j이면 [i-1][j] (이동하지 않은 경우) , [i-1][j-1] (이동한 경우) 중 큰 값과 (현재 위치에 따라 받을 수 있는 자두)를 더해서 최대 자두의 개수를 구할 수 있다. 

✅ 성공