본문 바로가기
알고리즘

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

by SiO2whocode 2020. 8. 12.
반응형

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

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

동적계획법 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;
}
반응형

댓글0