[백준(BOJ)] 18185 라면 사기(Small)

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

18185번: 라면 사기 (Small)

문제를 보고 그리디(Greedy) 알고리즘 문제라고 판단했는데 접근 방향은 좋았다.

 

먼저, 처음에 시도한 잘못된 접근 방법은 아래와 같다.

3개의 연속된 공장에서 라면을 구매할 수 있는 경우를 phase3

->연속 된 세 공장 중 최소 값 만큼을 세 공장 모두에서 구매(결과부터 얘기하자면 여기부터 잘못 접근했다...)

2개의 연속된 공장에서 라면을 구매할 수 있는 경우를 phase2

->연속 된 두 공장 중 최소 값 만큼을 두 공장 모두에서 구매

해당 공장에서만 라면을 구매할 수 있는 경우를 phase1으로 구분하였고

 

0번 째 라면 공장부터 시작하여

해당 공장(i번째)에 구매해야 할 라면이 있다면, 해당 공장에서 구매해야할 라면을 모두 구매할 때 까지

3, 2, 1 순으로 우선순위를 두어 phase를 수행하도록 했다. 

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

int n, cost;

void buy(int idx, vector<int>& noodleLab) {
	while (noodleLab[idx]) { //i번째 공장에서 구매해야 하는 라면을 모두 구매할 때 까지
   	    //1.연속된 3개 공장에서 구매 가능 한지 확인
		if (idx < n - 2) { 	//idx가 범위를 벗어나지 먼저 검사
			if (noodleLab[idx + 1] > 0 && noodleLab[idx + 2] > 0) { //가능하다면 세 공장에서 세 공장 중 최소 값 minCnt 만큼 구매
				int minCnt = *min_element(noodleLab.begin() + idx, noodleLab.begin() + idx + 2);
				noodleLab[idx] -= minCnt;
				noodleLab[idx + 1] -= minCnt;
				noodleLab[idx + 2] -= minCnt;
				cost += 7 * minCnt;
				continue;
			}
		}
        //2.연속된 2개 공장에서 구매 가능 한지 확인
		if (idx < n - 1) { //idx가 범위를 벗어나지 먼저 검사
			if (noodleLab[idx + 1] > 0) {
				int minCnt = *min_element(noodleLab.begin() + idx, noodleLab.begin() + idx + 1);
				noodleLab[idx] -= minCnt;
				noodleLab[idx + 1] -= minCnt;
				cost += 5 * minCnt;
				continue;
			}
		}
		cost += 3 * noodleLab[idx];
		noodleLab[idx] = 0;
	}
	
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	vector<int> noodleLab(n);
	for (int i = 0; i < n; i++) cin >> noodleLab[i];
	for (int i = 0; i <= n - 3;) {
		if (noodleLab[i] == 0) i++;
		else if
	}
	for (int i = 0; i < n; i++) {
		if (noodleLab[i]) { //i번 공장에서 구매해야 하는 라면이 있는 경우
			buy(i, noodleLab);
		}
	}
	cout << cost;
	return 0;
}

문제에 제시 된 테스트케이스는 만족했지만, 히든 케이스에 반례가 존재하여 실패하였다. 

간단한 반례로 1 2 1 1의 경우

최적 수행은 1 2 1 1 -> 0 1 1 1 (5원) -> 0 0 0 0 (7원) : 5 + 7 = 12원 인데,

앞의 두 공장에서 먼저 구매를 수행하는 것을 볼 수 있다. 

나의 로직은 1 2 1 1 -> 0 1 0 1 (7원) -> 0 0 0 1 (3원) -> 0 0 0 0 (3원) : 7 + 3 + 3 = 13으로 수행된다.

 

4시간 동안 반례를 찾아가며 로직을 수정했지만 결국 해결하지 못하고 레퍼런스를 찾아보게 되었다.

그 결과, 아래 두가지 상황을 나누어 고려해야 하는 것을 알게되었다.

①i+1번 공장 > i+2번 공장

②i+1번 공장 <= i+2번 공장

 

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

int n, cost, noodleLab[100001];

int main()
{
    ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> noodleLab[i];
    
    for (int i = 1; i <= n; i++) {
        if (noodleLab[i + 1] > noodleLab[i + 2]) {
            int a = min(noodleLab[i], noodleLab[i + 1] - noodleLab[i + 2]);
            cost += 5 * a;
            noodleLab[i] -= a; noodleLab[i + 1] -= a;

            int b = min(noodleLab[i], min(noodleLab[i + 1], noodleLab[i + 2]));
            cost += 7 * b;
            noodleLab[i] -= b; noodleLab[i + 1] -= b; noodleLab[i + 2] -= b;
        }
        else {
            int b = min(noodleLab[i], min(noodleLab[i + 1], noodleLab[i + 2]));
            cost += 7 * b;
            noodleLab[i] -= b; noodleLab[i + 1] -= b; noodleLab[i + 2] -= b;

            int a = min(noodleLab[i], noodleLab[i + 1]);
            cost += 5 * a;
            noodleLab[i] -= a; noodleLab[i + 1] -= a;
        }
        cost += 3 * noodleLab[i];
    }
    cout << cost << "\n";
    return 0;
}