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

N = int(input())
A = [*map(int,input().split())]

cost = i = 0
while i < N:
  if not A[i]:
    i += 1
    continue
  if i == N-1 or A[i+1] == 0:
    cost += A[i]*3
    i += 1
    continue
  if i == N-2 or A[i+2] == 0:
    cost += min(A[i],A[i+1])*5
    cost += abs(A[i]-A[i+1])*3
    i += 2
    continue
  if A[i+1]>A[i] and A[i+1]>A[i+2]:
    MIN = min(A[i],A[i+1]-A[i+2])
    cost += MIN*5
    A[i] -= MIN
    A[i+1] -= MIN
    continue
  MIN = min(A[i],A[i+1],A[i+2])
  cost += MIN*7
  A[i] -= MIN
  A[i+1] -= MIN
  A[i+2] -= MIN
print(cost)

처음으로 해결한 다이아 문제이다.

하지만 자력으로 해결했다고 하기에는 조금 부끄러운게, 그리디 알고리즘 문제라는걸 알고 풀었고, 반례도 참고해서 풀었다. 그리디 문제를 그리디라는 사실을 알고 풀면 난이도가 급감하는건 당연한 것이고, 이 문제 특성상 특정 반례를 참고하면 매우 쉽게 해결할 수 있는 문제라서 그렇다.

 

어쨌든 알고리즘을 설명하면,

1. 이 문제를 그리디하게 풀 수 있는 이유는 3+7=5+5 로 나타낼 수 있기 때문이다. 즉, 우선적으로 7을 사용한다는 것을 전체로 한다.

2. 1번에 대한 반례가 존재한다. 바로 1 2 1 1 이라는 반례인데, 1 2 1 1 >> 0 1 0 1 >> 0 0 0 0 의 비용보다 1 2 1 1 >> 0 1 1 1 >> 0 0 0 0 의 비용이 더 적다.

3. 따라서 이에 대한 조건분기를 나눠주어야 한다. 나는 현재 위치의 개수와 다음다음 위치의 개수가 다음 위치의 개수보다 적은 경우, 현재 위치에서 라면을 2개씩 사는 것으로 해결하였다. 이때 2개씩 사는 횟수는 현재 위치의 개수와 (다음 위치와 다음다음 위치의 차이) 중 더 작은 값이다.

4. 2,3에 해당하지 않는 경우 1번의 방법대로 그리디하게 해결한다.

 

 

오늘의 교훈) 문제를 완전 자력으로 해결할 수 있도록 노력하자