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

 

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

2579번: 계단 오르기

 

문제 요약

 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안된다.

3. 시작점은 계단에 포함되지 않는다.

4. 마지막 도착 계단은 반드시 밟는다.

 

1번째 밟고 2번째 혹은 3번째 계단 오를 수 있다.

1번째 밟고 4번째 혹은 2-3번째 계단을 연속으로 모두 밟을 수 없다.

이 게임에서 얻을 수 있는 총점수의 최댓값 구하기

 

범위 

 

계단의 개수 N (1 ≤ N ≤ 300)

 

 

 

---

 

 

 

N번째 계단에 도착해 얻는 최대 점수

→ 각 계단에 도착해서 얻을 수 있는 최대 점수를 구하면서 N번째까지 이동하면 N번째 계단에 도착해서 얻는 최대 점수를 구할 수 있다.

 

 

초기값은 계단 바로 밑부터 시작하므로 0에서 시작한다.

각 i번째 계단의 최대 점수를 담는 dp 이차원 배열을 선언한다.

dp [i][0] = i-2에서 한 칸을 건너뛰어 i로 올라온 경우의 점수

dp [i][1] = i-1에서 i로 올라온 경우의 점수

 

 

이런 문제는 규칙을 찾으면 쉽게 코드를 짤 수 있는데, 우선 규칙을 찾아보자.

i번째 계단에 도착할 수 있는 방법에 대해서 생각을 해보면 규칙이 나타난다.

 

5번 계단에 오른다고 생각해보자.

 - 4번 계단에서 오르는 경우(i-1에서 i로 올라오는 경우의 점수, dp [5][1]):

 

2번에서 4번, 5번으로 올라오는 경우는 가능하지만, 3번-4번-5번은 계단을 연속으로 밟는 경우이므로 무시한다. 2번에서 4번으로 오는 경우의 최대 점수 값은 dp [4][0] 이므로 

dp[5][1] = dp[4][0] + stair[5];

 

 - 3번 계단에서 오르는 경우(i-2에서 i로 올라오는 경우의 점수, dp [5][0]): 

 

이 부분은 2가지 경우가 모두 가능하다. 3번의 최대 점수를 찾아내서 그 값을 더해주면 되는데,

3번으로 오는 경우 두 가지, 2번에서 오는 경우와 1번에서 오는 경우 중 최댓값을 구하고 5번의 점수를 더해주면 된다.

dp[5][0] = stair[5] + max(dp[3][0], dp[3][1]);

 

 

다른 계단에서도 이와 같은 형식으로 진행이 되기 때문에 우리는 규칙을 찾을 수 있다!

dp[i][0] = stair[i] + max(dp[i-2][0], dp[i-2][1]);
dp[i][1] = stair[i] + dp[i-1];

 

초반의 값들은 고정값이 정해져 있다. 

1번 계단은 0보다 작은 값이 없으므로 dp [1][0] = 0, dp [1][1] = stair [1]로 지정해주었다.

또한 2번 계단도 1번에서 오는 경우와 시작점에서 오는 경우가 정해져 있기 때문에 지정해주되, 만약 계단의 개수(n)가 2보다 크거나 같은 경우에만 진행하도록 해주었다.

 

결괏값은 2가지 경우(i-1에서 온 경우, i-2에서 온 경우) 중 최대 점수를 낸 것을 출력해주었다.

 

#include <iostream>
#include <algorithm>
#define num 1002
using namespace std;
int n, stair[num], dp[num][2];

void input(){
    cin >> n;
    stair[0] = 0; //시작점
    for(int i=1; i<=n; i++) cin >> stair[i];
}

void solution(){
    dp[1][0] = 0; dp[1][1] = stair[1];
    if(n>=2){
        dp[2][0] = stair[2];
        dp[2][1] = stair[1] + stair[2];
    }
    
    for(int i=3; i<=n; i++){
        dp[i][0] = stair[i] + max(dp[i-2][0], dp[i-2][1]); //max 값을 넣어야 됨
        dp[i][1] = stair[i] + dp[i-1][0]; //3번 연속으로 오를 수 없기 때문
    }
    cout << max(dp[n][0], dp[n][1]) << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!