[백준] 2579번 계단오르기 -C++

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

2579번: 계단 오르기

 

다이나믹 프로그래밍(dp)를 이용해서 풀어야 하는 문제이다. 사실 아직 알고리즘 강의를 dp 부분을 안듣긴 했는데 점화식을 쓰는 부분이 마치 대입시절 수리논술을 공부하는 기분이 나서 풀어봤다.

 

처음 풀이

n번째 계단까지갈려면 아래와 같은 두가지 방법이 있다.

 

<방법1> n-2번째 계단 점수 + n번째 계단 점수
<방법2> n-1번째 계단 점수 + n번째 계단 점수

 

두가지 방법중 max(방법1, 방법2)가 답이 아닐까? 생각했고 그래서 이를 그대로 코드를 짰다.

코딩을 하다보니 문제 조건중에 세개의 계단을 차례대로 밟을 수 없다는 조건이 보였고, 이건 알아서 몇번째 연속으로 계단을 밟는지 count 하는 변수를 넣으면 되지 않을까? 생각해서 코드를 짰다.

#include <bits/stdc++.h>
using namespace std;

int a[301] ={0, };

//n번째 계단까지갈려면
//방법1 n-2번째 계단 점수 + n번째 계단 점수
//방법2 n-1번째 계단 점수 + n번째 계단 점수
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, t, cnt = 0;
    cin >> N;
    cin >> a[1];
    for(int i = 2; i <= N; i++){
        cin >> t;
        if(max(a[i-1]+t, a[i-2]+t) != a[i-2]+t){
            cnt++;//연속으로 밟는다 가정한다 ++
            if(cnt == 2){
                cnt = 0;
                a[i] = a[i-2]+t;
            }
            else{
                a[i] = a[i-1]+t;
            }
        }else{
            cnt = 0;
            a[i] = a[i-2]+t;
        }
    }
    cout << a[N] << '\n';
}

 

틀린이유가 뭘까 생각을 해보았는데, n-1번째 계단 -> n번째 계단을 갈 때, 경우에 따라 이미 n-2번째 계단을 밟았을 수도 있는 풀이이기 때문이다. 이를 고려하여 다음 내용을 코드로 짜서 제출했더니 통과했다.

 

<방법1> n-1번째 계단을 밟고 n번째 계단을 밟아야 한다면,

n-3번째 계단-> n-1번째 계단 -> n번째 계단(n-2번째 계단을 밟으면 안됨)

<방법2> n-2번째 계단을 밟고 n번째 계단을 밟아야 한다면,

n-2번째 계단 -> n번째 계단 (이전에 무슨 계단을 밟았는지 신경 쓸 필요X)

수정한 풀이

배열 a는 n번째 계단까지 갔을때 총점수의 최대값을 저장하는 배열이고, b는 입력값을 순서대로 저장하는 배열이다.

#include <bits/stdc++.h>
using namespace std;

int a[301] ={};
int b[301] ={};

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, t, cnt = 0;
    cin >> N;
    cin >> b[1];
    a[1] = b[1];
    if(N >= 2){
        cin >> b[2];
        a[2] = max(a[1] + b[2], a[0] + b[2]);
    }
    for(int i = 3; i <= N; i++){
        cin >> b[i];
        //n-1번째 계단을 밟고 n번째 계단을 밟아야 한다면, n-3번째 계단-> n-1번째 계단 -> n번째 계단
        int A = a[i-3] + b[i-1] + b[i];
        //n-2번째 계단을 밟고 n번째 계단을 밟아야 한다면, n-2번째 계단 -> n번째 계단
        int B = a[i-2] + b[i];
        a[i] = max(A, B);
    }
    cout << a[N];
}