[백준] 2579번 : 계단 오르기 [C/C++]

#문제

2579번: 계단 오르기

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

2579번: 계단 오르기

 

---

#접근방법

동적계획법으로 접근하였다.

반응형

---

#풀이

#include <stdio.h>
#include <algorithm>
using namespace std;

int arr[305];
int dp[305];

int main(){
    int n;

    scanf("%d",&n);

    for(int i=0;i<n;i++)
        scanf("%d",&arr[i]);

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

    printf("%d",dp[n-1]);

    return 0;
}

 

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있고 연속된 세 계단을 밟을 순 없다.

 

현재 계단에서 최대값이 될 수 있는 경우는 전 계단을 밟고 전전전 계단의 최대값, 그리고 전전 계단을 밟은 경우 둘 중에서 큰값이다.

 

이걸 코드로 옮기면 dp[i] = max(dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i])이다.

 

그러나 i가 3이상 부터 이 코드가 적용이 되므로 i가 0, 1, 2일 때는 따로 코드를 작성해주어서 예외처리를 하였다.

 

dp[n-1]을 출력하면 정답이다.

---

#성능

---

#정리

동적계획법을 사용해야 한다는 사실,

 

예외처리를 적절하게 하고 이를 구현할 수 있는 구현력이 있으면 풀 수 있는 문제였다.