백준 2579 계단 오르기 | Javascript | DP

고광필·2022년 5월 30일
0

알고리즘

목록 보기
10/12

백준 2579 계단 오르기

다이나믹 프로그래밍의 기초 문제입니다
풀기는 했으나, 오답과 정답간의 차이점이 무엇인지 몰라서 질문글을 올렸었고
어떤 분의 답변으로 놓친 부분을 깨닫게 되었습니다

문제

점프한 칸의 점수를 얻습니다
1칸 or 2칸 점프가 가능하고, 3칸 연속 점프는 불가능한 상황에서
마지막 칸까지 얻을 수 있는 가장 높은 점수를 구합니다

풀이

마지막 칸을 무조건 밟아야 한다1칸 or 2칸 점프라는 조건을 통해서
마지막 칸의 전칸 또는 전전칸을 밟는 경우로 나눠서 생각할 수 있습니다

마지막 칸의 전칸을 밟는 경우

마지막칸이 10칸이라고 하면
? => 9 => 10 이기 때문에 전전칸인 8칸을 밟고 올 수 없습니다
따라서 이 경우는 7 => 9 => 10
(target - 3) + (target - 1) + target이 됩니다

마지막 칸의 전전칸을 밟는 경우

마지막칸이 10칸이라고 하면
? => 8 => 10이기 때문에 3칸 연속 제한에 크게 걸리지 않습니다
따라서 이 경우는 (target - 2) + target

코드

내 풀이 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt";

let [count, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");
count = Number(count);
input = input.map(Number);

solution(input, count);

function solution(input, count) {
  const dp = Array(input.length).fill(0);
  dp[0] = input[0];
  dp[1] = input[0] + input[1];
  dp[2] = Math.max(input[0], input[1]) + input[2];

  for (let i = 3; i < input.length; i += 1) {
    dp[i] = Math.max(dp[i - 2] + input[i], dp[i - 3] + input[i - 1] + input[i]);
  }
  // console.log(dp);
  console.log(dp[count - 1]);
}

내가 놓친 점

오답과 차이를 몰랐습니다

오답 코드는 정답 확인 100%에서 오답처리 됩니다
마지막 dp[dp.length - 1]을 출력하는게 다른 부분입니다
dp의 마지막 값을 출력하기 때문에 같은 답이라고 생각해서 왜 오답인지 몰랐습니다

질문글을 올렸고 어떤 분의 답변으로
1개 또는 2개가 입력으로 주어질 때 오류가 발생함을 알게되었습니다
input은 1개나 2개가 들어왔지만, dp는 3개까지 정의되어 있기 때문에 오류가 발생하게 됩니다

참고

내가 올린 백준 질문글

profile
이해하는 개발자를 희망하는 고광필입니다.

0개의 댓글