[백준 2156] 알고리즘 44일차 : 포도주 시식

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

2156번: 포도주 시식

 

동적계획법 C++

계단 오르기 문제와 로직이 동일해보여서 풀기 시작했는데 닮은듯 달랐다.

계단오르기와 차이점은 우선 두칸이상 건너뛸 수 있다. (근데 사실상 세칸이상 건너뛰는 경우는 없다. 가운데 하나를 먹어야 이득이니까)

그리고 꼭 마지막 주스를 먹어야할 필요가 없다. (최종 값을 출력할때 n-1칸과 n-2칸의 값을 비교해서 출력해야함)

 

차이점은 두갠데 그래서 많은 것이 추가됐다..

접근방법은 계단 오르기와 동일하고 이번에는 그냥 배열 전체를 다썼다. shift하는게 더 비용이 많이 들 것 같아서

계단오르기에서는 한칸 만 건너뛸 수 있지만 여기선 두칸까지 건너뛰는 경우를 고려해야해서

값을 비교할때 n-2, n-3 까지 비교한다. 

 

하지만 1,2,3일 경우를 고려해야해서 코드가 아주 더럽게 짜졌다.

실질적인 로직부분은 6줄인데 1,2,3 경우 처리에 20줄을 썼다..;;;

배보다 배꼽이 더 큰 코드..

최악의 코드지만 고칠 생각은 없다..우당탕탕 잘돌아가긴 한다..

절대 참고하지 않길 바람

 

소스코드

#include <iostream>
using namespace std;

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