[C++] 18185. 라면사기

<문제>

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

 

 

처음에는 단순한 그리디 문제라고 생각해서, 3번방법을 최우선으로 문제를 풀었다가 완전히 막혀버렸다

계속 고민하다가 찾아보니, 반례가 있다더라

반례 케이스를 설명해보자면, 3번 방법을 사용할 수 있는 상태인데, i+2보다 i+1이 더 큰 경우이다

 

예시
A[4] = 1 2 1 1

 

1. 3번 방법 우선시
   A[0], A[1], A[2] -> 7
   A[1], A[3]이 1씩 남으므로 -> 3 * 2 = 6
   ==> 7 + 6 = 13
2. 2번 방법 우선시
   A[0], A[1] -> 5
   A[1], A[2], A[3] -> 7
   ==> 5 + 7 = 12

이렇게 반례가 생겨버린다.. 안 찾아봤으면 절대 몰랐을듯..

 

아무튼, 이 반례를 적용해주려면 i+2랑 i+1 크기 비교하고, i+1이 더 큰 경우 2번 방법을 우선 진행 후 순차적으로 원래 생각했던 그리디 방식을 적용하면 된다. (3->2->1 방법 순으로 진행)

 

코드를 보면 이해가 더 쉬울것 같다.

 

[코드]

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
i번 3원
i, i+1 5원
i, i+1, i+2 7원
i번에서 Ai개 구매
1. 3번 방법이 무조건 최소금액임 -> Greedy
2. Ai 확인하기

<반례 케이스>
3번 구매가능 + i+1가 더 많을때
예) 1 2 1 1
3번먼저 -> 7 + 3 + 3 = 13
2번먼저 -> 5 + 7 = 12
*/

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, result = 0;
    cin >> N;
    vector<int> A(N);

    for(int& x : A) cin >> x;

    for(int i=0; i<N-2; i++) {
        if(A[i+1] > A[i+2]) {
            int two = min(A[i], A[i+1]-A[i+2]);
            A[i] -= two;
            A[i+1] -= two;
            result += 5 * two;
        }
        int three = min({A[i], A[i+1], A[i+2]});
        A[i] -= three;
        A[i+1] -= three;
        A[i+2] -= three;
        result += 7 * three;
            
        int two = min(A[i], A[i+1]);
        A[i] -= two;
        A[i+1] -= two;
        result += 5 * two;

        result += 3 * A[i];
        A[i] = 0;
    }

    // 마지막 2칸(N-2, N-1) 계산
    int last = min(A[N-2], A[N-1]);
    result += 5 * last;
    A[N-2] -= last;
    A[N-1] -= last;

    result += 3 * (A[N-2] + A[N-1]);

    cout << result << "\n";
}

 

 

여기서 또 잊을뻔한게, 반복문이 N-2까지만 돌기 때문에, 맨 마지막 두개(A[N-2], A[N-1])를 따로 계산해줘야한다. (이거 빼먹어서 또 틀렸다..ㅋㅋㅋ)

마지막까지 계산 완료하면 끝!

 

그리디를 너무 일차원적으로만 생각해서 헤맨 문제였다.

다음에는 반례가 있을 가능성을 먼저 생각하면서 문제를 풀면 더 수월할 것 같다.