2579 - 계단 오르기

• 난이도: 실버 3
• 날짜: 2023년 3월 12일
• 상태: Correct
• 추가 검토 여부: No
• 알고리즘 : Dynamic Programming

Solution

• 처음 문제를 읽고 동적 프로그래밍 문제인 지 바로 인식하지 못해 문제 풀이에 시간이 걸렸다.
• 1칸, 2칸, 3칸, 4칸에 대하여 가능한 경우의 수를 손으로 직접 그려보니 동적 계획법 문제인 것이 바로 인식되었다. 경우를 나누어 배열을 초기화했다.
  • n번째 계단에 도착했을 때 직전 계단에 이어 연속해서 밟는 경우
  • n번째 계단에 도착했을 때 직전 계단을 건너뛰고 두 칸 이전의 계단에서 이어 밟는 경우
• 상황을 크게 위의 두 가지 경우로 나누어 생각할 수 있다.
• pair를 사용하여 first에는 직전 계단에 연속해서 밟는 점수를 저장했다. second에는 두 칸 이전의 계단에서 이어 밟았을 때의 점수를 저장했다.
  • 직전 계단에서 이어 밟았을 경우, 직전 계단 이전의 계단을 밟은 경우라면 3칸을 연속해서 밟은 상황이 되기 때문에 이를 생각해서 직전 계단의 second와 n번째 계단의 점수를 더해야 한다. first는 고려하지 않는다.
  • 두 칸 이전의 계단에서 이어 밟았을 경우에는, 두 칸 이전의 계단이 이전 계단에서 어떻게 넘어왔는지는 중요하지 않으므로 first, second중 큰 값에 대해 n번째 계단의 점수를 더해 second에 저장했다.
• 설명이 복잡하여 아래의 그림으로 간단하게 정리해 보았다. 결과적으로 65보다 75가 크기 때문에 테스트 케이스에서의 정답인 75를 출력하게 된다.

code

#include <iostream>
#include <utility>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int * arr = new int[N];
    for(int i = 0; i < N; i++)
        cin >> arr[i];
    
    pair<int, int> * ans = new pair<int, int>[N];
    ans[0].first = arr[0]; ans[0].second = arr[0];
    ans[1].first = arr[1] + arr[0]; ans[1].second = arr[1];
    for(int i = 2; i < N; i++)
    {
        ans[i].first = ans[i-1].second + arr[i];
        ans[i].second = (ans[i-2].first < ans[i-2].second) ? ans[i-2].second + arr[i] : ans[i-2].first + arr[i];
    }
    
    
    int answer = ans[N-1].first < ans[N-1].second ? ans[N-1].second : ans[N-1].first;
    cout << answer << endl;

    return 0;
}

ref

2579번: 계단 오르기