#2579 계단 오르기

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

2579번: 계단 오르기

실버 3의 문제이다. 항상 느끼지만 dp는 감을 잡기가 어려운것 같다. 이 문제도 한참을 고민하다가 코드를 짰는데 틀리고, 다시 고민하다가 결국 정답코드를 보았다. 😥

#include <iostream>
#include <algorithm>
using namespace std;

int dp[301];
int score[301];

int main()
{
  freopen("input.txt","r",stdin);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>score[i];
  }

  dp[1]=score[1];
  dp[2]=score[1]+score[2];

  for(int i=3;i<=n;i++){
    dp[i]=max(dp[i-2]+score[i],dp[i-3]+score[i-1]+score[i]);
  }

  cout<<dp[n]<<'\n';
}

일단 계단의 점수를 담을 score배열을 선언해주고, 점수를 담을 dp배열도 선언해주었다. 

각 계단의 점수를 입력 받고 score에 저장해주었다.

이제 어떻게 코드를 구성할 지 생각해보아야 한다. 나는 점화식을 세우고자 했고, D(n) = n개 계단이 있을때 최대 점수 라고 두고 생각했다. 마지막 계단은 반드시 밟아야 하니, 이 문제는 1을 n으로 만드는 문제가 될수 있겠다 생각했다. 방법은 두가지가 있고, +1과 +2였다.

이 생각은 문제점이 있었다. 연속된 3개의 계단은 밟을 수 없다는 조건을 충족시키기가 매우 어려웠다.. 그래서 일단 그 조건을 빼고 코드를 구성했는데 당연히 틀렸다.

 

일단 계단은 4개라고 가정, 점수는 각각 1,2,3,4점이라고 둔다.

1. 첫번째 계단까지 올라갔을때

최댓값은 당연히 첫번째 계단의 점수인 1점이다.

 

2. 두번째 계단까지 올라갔을때

최댓값을 계산해보자. 경우의 수는 두가지가 있다.

첫째, 1번계단 + 2번계단

둘째, 2번계단.

최댓값은 당연히 첫째의 경우이다. 계단의 점수는 0이거나 음수이지 않기 때문이다. (조건에, 10000 이하의 자연수라고있음)

 

3. 세번째 계단까지 올라갔을때

경우의수를 살펴보자.

1번 계단 + 2번계단 + 3번계단  (불가능, 연속된 세개의 계단은 밟을 수 없다!)

1번계단 + 3번계단

2번계단 + 3번계단

 

이 두가지 경우의 수 중에 최대값을 선택하면 되므로 간단히 max( 1번계단+3번계단 , 2번계단+3번계단) 으로 쓸 수 있다.

 

4. 네번째 계단까지 올라갔을때

경우의수를 살펴보자.

1번계단 + 2번계단 + 4번계단

1번계단 + 2번계단 + 3번계단 + 4번계단  (불가능, 3개의 연속된 계단은 밟을 수 없다!)

1번계단 + 3번계단 + 4번계단

 

위의 두가지 경우 중에 최대값을 선택하면 된다. 이때, 첫번째 경우에서 1번계단 + 2번계단 은 두번째 계단까지 올라갔을때의 값이므로 dp[2]로 쓸수 있다. 그렇다면 두번째 경우에서 1번계단 + 3번계단 을 dp[3]이라고 쓸 수 있을까? 그렇지 않다. 3번째 계단까지 올라갔을때는 두개의 경우가 나오고 그중 최대값을 선택해야 하기 때문이다. 따라서 문제를 더 쪼개서 1번계단 을 dp[1]로 쓴다.

결론적으로 max( dp[2] + 4번계단 , dp[1] + 3번계단 + 4번계단) 으로 쓸 수 있다.

 

이때, 4를 n으로 바꾼다면 다음과 같이 쓸 수 있다.

max( dp[n-2] + score[n] , dp[n-3] + score[n-1] + score[n] ) 이 식이 5번째에도 적용되는지 검사해본다.

 

5. 다섯번째 계단까지 올라갔을때

경우의 수를 살펴보자.

1번계단 + 2번계단 + 4번계단 + 5번계단 = 12

1번계단 + 3번계단 + 5번계단 = 9

2번계단 + 3번계단 + 5번계단 = 10

2번계단 + 4번계단 + 5번계단 = 11

이므로 max( dp[3] + score[5] , dp[2] + score[4] + score[5] ) 과 맞는다는 것을 볼 수 있다. 

 

💻 배운 것

1. 점화식에 연연하지 말자.

점화식을 세워 푸는 문제인 것은 맞지만, 점화식에 연연해서 실제로 써보지 않는 짓은 하지말자. 최고의 방법은 직접 써보는 것일 수도 있다!

 

2. 문제는 쪼갤 수 있을때까지 쪼갠다!

위의 문제에서 4번째 단계에서 dp[1]로 쓰지않고 score[1]이라고 단순히 썼다면 정답은 나오지 않는다. 가능한 한 끝까지 쪼개서 작은 문제로 만든다.