[BOJ] 18185. 라면 사기 (Small)

문제

---

최대한 연속되게 라면을 구매하는 것이 이득이다.

포인트

---

i 번째에서 i + 2 가 유효한지 확인한 후 i, i+1, i+2 중 가장 최소 값을 구해서 3연속으로 라면을 구매하고 i, i+1 중에서 최소값으로 2연속 라면을 구매하고 나머지 라면을 구매하는 방식으로 구현했다.

하지만 4 2 3 2 1

의 예시에서 (2 2 2 0) -> (0 1 0 1) 로 14 + 6 = 20원 보다 (1 1 0 0) -> (1 1 1 0) -> (0 1 1 1) 로 5 + 14 = 19원이 더 이득임을 확인할 수 있다.

현재 1 2 1 에서 (1, 1, 1) (0, 1, 0) 과 (1, 1, 0) (0, 1, 1) 이 동일한 10원임을 알 수 있다. 이때 라면은 앞쪽부터 구매하기 때문에 후자의 방식의 (0, 1, 1)이 추후에 (0, 1, 1, 1) 이 될 가능성이 있다.

따라서 f(i+1) > f(i+2) 인 경우에 min(f(i), f(i+1) - f(i+2)) 만큼 2번 연속으로 라면을 구매하고 원래 알고리즘을 적용시킨다.

코드

---

n = int(input())
factory = list(map(int, input().split()))

total_cost = 0

for i in range(n):
    if factory[i] > 0:
        if i + 2 < n and factory[i + 2] > 0:
            if factory[i + 1] > factory[i + 2]:
                dif = factory[i + 1] - factory[i + 2]
                dif = min(factory[i], dif)
                total_cost += dif * 5
                factory[i] -= dif
                factory[i+1] -= dif

            minR = min(factory[i], factory[i+1], factory[i+2])
            total_cost += 7 * minR
            factory[i] -= minR
            factory[i + 1] -= minR
            factory[i + 2] -= minR

        if i + 1 < n and factory[i + 1] > 0:
            minR = min(factory[i], factory[i+1])
            total_cost += 5 * minR
            factory[i] -= minR
            factory[i + 1] -= minR

        total_cost += 3 * factory[i]
        factory[i] = 0

print(total_cost)