백준 2579 - 계단 오르기

문제

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

2579번: 계단 오르기

 

 

풀이

연속해서 세 개의 계단을 밟을 수 없으므로 n번째 계단에서 가능한 경우는 두 가지가 있다.

1. n-1번째 계단과 n번째 계단을 밟는 경우

2. n-2번째 계단과 n번째 계단만 밟는 경우

 

d[n] = n번째 계단을 포함하는 n번째 계단까지 점수의 최대값 이라고 하면

d[n] = {

    max(1번 경우, 2번 경우)

} 가 된다.

 

1번의 경우 n-3 번째 계단 까지 밟은 경우가 되고, 2번의 경우 n-2 번째 계단까지 밟은 경우가 된다.

 

따라서 d[n] = {

    max(d[n-3] + arr[n-1] + arr[n], d[n-2] + arr[n])

}

이 된다.

 

코드

 

탑다운 방식

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n;
int arr[301];
int dp[301];
 
int f(int n)
{
    if (dp[n]) return dp[n];
    if (n == 1 || n == 0) return arr[n];
    if (n == 2) return arr[1] + arr[2];
    return dp[n] = max(f(n - 3) + arr[n - 1] + arr[n], f(n - 2) + arr[n]);
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    cout << f(n);
 
    return 0;
}
 

 

바텀업 방식

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n;
int arr[301];
int dp[301];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
    for (int i = 3; i <= n; i++)
    {
        dp[i] = max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i]);
    }
 
    cout << dp[n];
 
    return 0;
}