백준 18185 라면 사기 (Small)

1. 문제 설명

총 N개의 라면 공장이 있으며, 각 공장에서 구매해야 할 라면의 수 Ai가 주어집니다. 구매 방식은 다음 세 가지입니다:

• 1개 공장에서 라면 1개: 3원
• 2개 연속된 공장에서 각 1개씩: 5원
• 3개 연속된 공장에서 각 1개씩: 7원

2. 초기 아이디어: 개당 단가가 싼 3개 묶음 우선?

각 방식의 개당 단가는 다음과 같습니다:

• 1개 묶음: 3원 (개당 3원)
• 2개 묶음: 5원 (개당 2.5원)
• 3개 묶음: 7원 (개당 약 2.33원)

그래서 대부분은 3개 묶음을 우선 사용하는 전략을 떠올리지만, 이 전략은 일부 경우에 손해를 볼 수 있습니다.

3. 예상치 못한 '함정'과 반례

📌 반례 1

입력: N = 4, A = [2, 3, 2, 1]

공장 위치	초기 라면 수	처리 내용	비용	누적 비용
0~2	[2, 3, 2]	3개 묶음 × 2 → [0, 1, 0]	7 × 2 = 14	14
1	[1, 0]	1개 묶음 × 1 → [0]	3 × 1 = 3	17
3	[1]	1개 묶음 × 1 → [0]	3 × 1 = 3	20

더 나은 방법: 2개 묶음을 먼저 사용하면 총 19원으로 구매 가능합니다.

📊 반례 1 전체 실행 과정 (입력: A = [2, 3, 2, 1])

단계	i	A 상태	조건 판단	실행된 구매	비용	누적 비용
1	0	[2, 3, 2, 1]	A[1] > A[2] → 3 > 2 → ✅	2개 묶음: min(2, 3 - 2) = 1 → A[0] -=1, A[1] -=1	5	5
2	0	[1, 2, 2, 1]	3개 묶음 구매 가능: min(1,2,2)=1	3개 묶음 1회 구매 → A[0] -=1, A[1] -=1, A[2] -=1	7	12
3	0	[0, 1, 1, 1]	A[0] == 0 → 스킵	-	0	12
4	1	[0, 1, 1, 1]	A[2] <= A[3] → 1 <= 1 → ✅	3개 묶음 1회 구매 → A[1] -=1, A[2] -=1, A[3] -=1	7	19
5	1	[0, 0, 0, 0]	A[1] == 0 → 스킵	-	0	19
6	2	[0, 0, 0, 0]	A[2] == 0 → 스킵	-	0	19
7	3	[0, 0, 0, 0]	A[3] == 0 → 스킵	-	0	총합: 19

이처럼 그리디 전략에 따라 2개 묶음을 먼저 선택하고 이후 3개 묶음을 적용하면 정확히 19원으로 라면을 모두 구매할 수 있습니다.

📌 반례 2

입력: N = 4, A = [3, 5, 2, 0]

공장 위치	초기 라면 수	처리 내용	비용	누적 비용
0~2	[3, 5, 2]	3개 묶음 × 2 → [1, 3, 0]	7 × 2 = 14	14
0~1	[1, 3]	2개 묶음 × 1 → [0, 2]	5 × 1 = 5	19
1	[2]	1개 묶음 × 2 → [0]	3 × 2 = 6	25

반면, 단순히 3개 묶음만 사용하면 마지막에 남은 라면을 1개 묶음으로 처리해야 해 27원까지 소요될 수 있습니다.

 

---

📌 요약

이처럼 A[i+1] > A[i+2]인 경우, 먼저 2개 묶음을 처리하지 않으면 남은 라면을 비싸게 사야 하는 상황이 생깁니다. 따라서 이런 패턴을 인식하고 그에 맞는 전략을 적용하는 것이 최소 비용을 구하는 핵심입니다.

💡 왜 A[i+1] > A[i+2] 조건이 필요한가?

그리디 전략에서 3개 묶음을 우선 사용하는 방식은 대부분의 경우 유리하지만, 특정 조건에서는 손해를 유발합니다. 대표적인 경우가 바로 A[i+1] > A[i+2]인 상황입니다.

📌 손해 발생 비교표

전략초기 상태구매 순서남는 수량총 비용

3개 묶음 우선	[2, 3, 2, 1]	3개 묶음 × 2 → 1개 묶음 × 2	A[1]=1, A[3]=1	20
2개 묶음 우선	[2, 3, 2, 1]	2개 묶음 × 1 → 3개 묶음 × 2	없음	19

📊 전략 비교 애니메이션 도식 (의사 애니메이션)

[초기]   A = [2, 3, 2, 1]

① 잘못된 전략: 3개 묶음 우선
   [2, 3, 2] → 3개 묶음 2회 → A = [0, 1, 0, 1]
                                  ▲     ▲
                                 남음   남음

② 개선 전략: 2개 묶음 우선
   A[1] > A[2] → 2개 묶음 1회 → A = [1, 2, 2, 1]
   그 후 3개 묶음 2회 → A = [0, 0, 0, 0] ✅

🧮 수식으로 보는 찌꺼기 비용 발생

3개 묶음 사용 시 가능한 수량은 다음과 같습니다:

최대 구매 수량:   k=min(A[i],A[i+1],A[i+2])

하지만, 만약 A[i+1] > A[i+2] 라면,

• A[i+1]에 찌꺼기 수량이 남게 됨
• 이 수량은 이후 묶음 구성에 쓸 수 없고 → 결국 1개 묶음(3원)으로 처리

✅ 조건 요약

조건의미전략

A[i+1] > A[i+2]	3개 묶음 사용 시 A[i+1]이 남음	2개 묶음 우선
A[i+1] ≤ A[i+2]	3개 묶음을 사용해도 남는 수 없음	3개 묶음 우선

이처럼, 그리디 알고리즘에서도 단순히 '단가 낮은 것 먼저'가 아니라 남는 수량이 향후 전략에 어떤 영향을 미치는지까지 고려해야 진정한 최소 비용을 달성할 수 있습니다.

단순히 3개 묶음부터 구매하는 전략은 어떤 경우에는 더 많은 비용을 초래할 수 있습니다. 아래는 실제 반례를 표로 시각화한 것입니다.

4. 진짜 그리디 전략

핵심은 3개 묶음이 항상 정답이 아니라는 것입니다. 아래와 같은 전략이 필요합니다:

• Case 1: A[i+1] > A[i+2]이면 → 2개 묶음 우선
• Case 2: A[i+1] ≤ A[i+2]이면 → 3개 묶음 우선

각 경우에 따라 다음 순서로 처리합니다:

1. 해당 조건에 따라 2개 또는 3개 묶음부터 구매
2. 이후 가능한 묶음을 순서대로 처리
3. 남은 라면은 1개 묶음으로 처리

5. 파이썬 코드 구현

다음은 위 알고리즘을 구현한 파이썬 코드입니다:

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split())) + [0, 0]  # 패딩

ans = 0

for i in range(N):
    if A[i] > 0:
        if A[i+1] > A[i+2]:
            buy2_first = min(A[i], A[i+1] - A[i+2])
            ans += buy2_first * 5
            A[i] -= buy2_first
            A[i+1] -= buy2_first

        buy3 = min(A[i], A[i+1], A[i+2])
        ans += buy3 * 7
        A[i] -= buy3
        A[i+1] -= buy3
        A[i+2] -= buy3

        buy2 = min(A[i], A[i+1])
        ans += buy2 * 5
        A[i] -= buy2
        A[i+1] -= buy2

        ans += A[i] * 3
        A[i] = 0

print(ans)

코드에서는 배열 패딩을 통해 경계 문제를 방지하고, 조건에 따라 2개/3개 묶음의 구매 순서를 유연하게 조절합니다.

6. 마무리

이 문제는 전형적인 그리디 문제처럼 보이지만, 반례 분석을 통해 전략을 정교하게 다듬는 과정이 필요합니다. A[i+1] > A[i+2]와 같은 조건을 인식하고 이에 따라 전략을 바꾸는 것이 최소 비용 해결의 핵심입니다.