🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs
.readFileSync(path)
.toString()
.trim()
.split('\n')
.map(Number);
const n = inputs.shift();
const dp = Array.from({ length: n + 1 }, () => Array(3).fill(0));
for (let i = 1; i <= n; i++) {
dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = dp[i - 1][0] + inputs[i - 1];
dp[i][2] = dp[i - 1][1] + inputs[i - 1];
}
console.log(Math.max(dp[n][1], dp[n][2]));
🟢 풀이
⏰ 소요한 시간 : -
문제 딱 보고 dp인데 내가 못풀겠다 싶어서 풀이를 봤다.
다차원 배열사용 + 계단을 밟거나 안밟거나를 따져서 조건 계산인건 알겠는데 식이 안세워짐 ㅠㅠ
아무튼 이 문제의 핵심은 계단을 밟거나, 안밟거나로 따져준다.
근데 내가 이전에 계단을 두 번 연속으로 밟았다면 다음에는 반드시 안밟아야 한다는 조건이 있다.
그래서 내가 계단을 연속으로 0번 밟았을 때, 1번 밟았을 때, 2번 밟았을 때로 나누어 계산한다.
위 표의 열 속성 즉, 0, 1, 2는 각각 연속으로 밟은 계단의 횟수이고 행 속성인 0~6은 층에 대한 정보이다.
표의 값은 내가 i번 층을 j번 연속으로 밟았을 때의 점수 값이다.
문제의 예제처럼 시작 층을 0층이라고 가정하고 0번 밟았다고 가정한다.
위 사진처럼 첫 층을 연속으로 0번 밟았을 경우, 1층은 안밟은 것이기 때문에 획득한 점수가 없다. 반면 1번 연속, 2번 연속으로 밟았다고 가정하면 해당층의 10점을 획득할 수 있다.
다음층에서 첫 층을 연속으로 0번 밟으려면 이전에 무조건 밟은 흔적이 있어야 한다.
그래서 1번 연속으로 밟았을 때인 10과 2번 연속으로 밟았을 때인 10중 최대값을 가져온다.
연속으로 1번 밟으려면 무조건 이전에 0번 밟았어야 하므로 이전의 점수인 0과 현재 층의 점수인 20을 더해 20점을 얻을 수 있다.
연속으로 2번 밟으려면 무조건 이전에 1번 밟았어야 하므로 이전 점수인 10과 현재 층의 점수인 20을 더해 30점을 얻을 수 있다.
위와 같은 방식으로 표를 다 채워준 후 가장 마지막 층은 무조건 밟고 있어야 하므로 Math.max(dp[n][1], dp[n][2]) 둘중 큰 값을 선택해주면 된다.
🔵 Ref
