DP 문제 시도하기(+ 백준 2579 계단오르기)

1. 문제

- https://www.acmicpc.net/problem/2579

 

 

2. 생각해보기(알고리즘)

A. 해당 문제가 DP 문제인 이유

1)  🧩 이전의 계단 점수의 합들을 더해서 답을 찾아야 하기 때문(단순히 분할정복 알고리즘이 아닌 이유)

2) 🥇 총 점수의 최댓값 => 최적의 해를 구해야 하기 때문

3) 🚨 놓친 부분 : 연속 횟수 제약(중복 부분 문제의 변형)
    +1은 연속해서 3번은 불가능하다. => 최대 점수를 계산할 때 반드시 직전 계단을 연속으로 몇 번 밟았는지 과거 이력을 알아야 함. 

    과거 이력을 알아야 함 = 저장해야 함 = 중복되는 부분 문제 개선필요 = DP 테이블 필요

 

 

😵‍💫 처음부터 풀려고 하니까.. 모르겠습니다..

나눠서 생각해보는 방향으로 고민해봤습니다.

(답은 아니고, 제 스스로 시도한 방법으로 적어놓았습니다.

다음과 같은 방향으로 시도하시지 마시고 어떻게 풀지는 스스로 고민해보시길 바랍니다!)

 

 

B. 한번에 +1칸 +2칸 갈 수 있는 경우의 수

DP[n] = DP[n-1] + DP[n-2]

1부터 5까지 경우의 수 구하기

n	경우의 수	케이스
1	1	(1)
2	2	(1,1), (2)
3	2	(1,2), (2,1)
4	4	(1, 2, 1), (2, 2), (2, 1, 1), (1, 1, 2)
5	6	(2, 2, 1), (1, 1, 2, 1), (2, 1, 2), (1, 2, 2)...

=> n은 결국 (n-1) + (n-2)의 경우의 수를 더해서 경우의 수가 만들어짐

 

코드로 작성해보기

const step = (num : number) => {
    if(num <= 0) return 0;
    return step(num-1) + step(num-2);
}

console.log(step(n)); // n의 앞에서 계단 개수

 

 

C. 경우의 수가 아니라 계단 점수의 합으로 변경

const stepList = [0].concat(input.slice(1).map(Number)); // 0번방 : 0, 1번방부터 input 계단 점수로 채우기
const step = (num : number) => {
     if(num <= 0) return 0;
     return stepList[num] + step(num-1) + step(num-2);
}

=> 모든 경우의 수에 대한 합이네..

 

D. 최대값을 구하려면

step(num-1), step(num-2)한 값에서 Math.max()를 사용해서 둘 중에 더 큰 값을 사용한다. 

 

 

E. 1이 연속해서 3번이 등장하면 안되는 조건 추가

=> 2가지 필요함. 
1) DP 값을 저장해야 함. (중복 관리)

2) +1을 한 케이스하고 +2를 한 케이스를 분리해서 저장해야 함. 

 

보통 탑다운 형태의 코드를 많이 작성한다고 합니다. 

 

const dp: number[][] = Array.from({ length: n + 1 }, () => [0, 0, 0]);

if (n === 1) {
     console.log(stepList[1]);
} else {
     dp[1][1] = stepList[1];
     dp[1][2] = 0; // 연속 2칸 개념 없음
     dp[2][1] = stepList[2]; // 0->2
     dp[2][2] = stepList[1] + stepList[2]; // 0->1->2

     for (let i = 3; i <= n; i++) { // 한 계단 건너(i-2)에서 오는 경우: 연속 1칸
           dp[i][1] = Math.max(dp[i - 2][1], dp[i - 2][2]) + stepList[i]; // 바로 이전(i-1)에서 오는 경우: 연속 2칸이 되므로 이전은 반드시 연속 1칸이어야 함
           dp[i][2] = dp[i - 1][1] + stepList[i];
      }
      console.log(Math.max(dp[n][1], dp[n][2]));
}

 

=> 처음 풀어보는 알고리즘이라면, 풀릴때까지 계속 생각하는게 아니라, 30분 고민해보고 다른 사람들은 어떻게 푸는지를 보고 다시 생각해보는 방향이 조금 더 도움이 될거라는 조언을 받았었습니다. 처음에는 스스로 생각해보고(물론 방향이 잘못되었기는 했지만요..) 답을 보니 왜 이렇게 풀어야 하는지 하고 제 코드는 왜 안되는지를 발견하게 되었습니다. 시간이 굉장히 많이 걸리는 일이지만, 다음 문제 풀때 길을 빠르게 잡게 되어 좋은 것 같습니다. 해당 방법으로 시도해보시기를 추천 드립니다. 

 

3. 결과

https://github.com/moonlight-duck/study-algorithms/pull/23

feat: 백준 2579(DP) 계단 오르기 by min-99 · Pull Request #23 · moonlight-duck/study-algorithms

 

제출결과

 

[참고 동영상 study]

https://www.youtube.com/watch?v=qLkFBk5-HrY&t=2s