https://www.acmicpc.net/problem/2240
2240번: 자두나무
자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어
www.acmicpc.net
📌 작성한 코드
// 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] (이동한 경우) 중 큰 값과 (현재 위치에 따라 받을 수 있는 자두)를 더해서 최대 자두의 개수를 구할 수 있다.

✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript] 백준 골드 4 : 20056 - 마법사 상어와 파이어볼 (1) | 2024.03.01 |
|---|---|
| [JavaScript] 백준 골드 4 : 14499 - 주사위 굴리기 (0) | 2024.03.01 |
| [JavaScript/Greedy] 백준 골드 4 : 1744 - 수 묶기 (0) | 2024.02.29 |
| [JavaScript/이분탐색] 백준 실버 2 : 1654 - 랜선 자르기 (1) | 2024.02.28 |
| [JavaScript/BFS/백트래킹] 백준 골드 3 : 1941 - 소문난 7공주 (1) | 2024.02.28 |