[백준 2579] 알고리즘 42일차 : 계단 오르기

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

2579번: 계단 오르기

동적계획법 C++

연속으로 세칸을 오를 수 없고 / 그림처럼 한 칸 혹은 두 칸씩 오를 수 있다.

각 계단 마다 점수가 배정돼있고 위의 규칙을 지키면서 그 점수의 합이 최대가 되는 경우 최댓값을 출력하기

 

접근방법

이 문제도 작은 부분에서의 최댓값을 구해가면서 풀었다.

각 칸에서의 최댓값을 저장하면서 갱신해갔다.

해당 칸에서 그 전칸의 최댓값, 그 전전칸의 최댓값을 비교해가면서 저장해간다.

너무 추상적으로 썼는데 구체적으로는

배열은 2x2배열을 사용했고 각 행은 n-1칸, n-2칸을 의미한다.

0열은 연속으로 오른 계단의 수가 1일때의 최댓값

1열은 연속으로 오른 계산의 수가 2일때의 최댓값을 저장한다.

 

예를 들어 세번째 칸에서는 두번째 칸까지 연속으로 오른 계단 수가 1인 경우 점수의 최댓값을

(연속으로 오른 계단의 수가 2인 경우 세번째 칸을 오르게 되면 세번연속으로 계단을 오르는 경우이기 때문)

세번째 칸까지 연속으로 오른 계단의 수가 2인 경우 점수의 최댓값에 저장한다.

그리고 첫번째 칸까지 연속으로 오른 계단 수가 1,2인 경우 점수의 최댓값을 비교해서 큰 값을

세번째 칸까지 연속으로 오른 계단의 수가 1인 경우 점수의 최댓값에 저장한다.

(두 칸 전에서 한 칸을 건너뛰고 오르는 경우이기 때문에 연속된 계단의 수는 상관없다.)

 

으 설명을 정말 못하겠다. 이번 문제는 특히 나만 알아볼 수 있게 풀었으니까..차라리 그림으로 이해하는게 더 빠를듯 싶다.

한번에 통과돼서 매우 기쁜 상태

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    
    int arr[2][2] = {0,};
    int score1, score2;
    int score;
    for(int i = 0 ; i < n ; i++){
        score1 = max(arr[0][0], arr[0][1]);
        score2 = arr[1][0];
        cin >> score;
        arr[0][0] = arr[1][0];
        arr[0][1] = arr[1][1];
        arr[1][0] = score+score1;
        arr[1][1] = score+score2;
    }
    cout << max(arr[1][0], arr[1][1]);
    return 0;
}