[백준] 13305번

문제출처: https://www.acmicpc.net/problem/13305

13305번: 주유소

 

미루고 미루던 그리디 알고리즘 문제이다.

문제를 요약하면, 원하는 도시까지 도달하는데 필요한 최소의 주유비를 구하는 것이다.

가령 예시처럼 4개의 도시가 있고 마지막 도시에 도달하고 싶을 때,

최소한으로 1리터당 5원하는 맨 첫번째 도시에서 5x2=10원 충전을 필수로 하고

그 다음 가장 주유비가 저렴한 곳에서 나머지 리터당 주유를 채우면 된다.

다만, 제일 오른쪽 거리는 최종 도달점이므로 주유지에서 제외한다.

​

난 맨 첫번째에서 필수적으로 채우는 값을 시작점으로 삼고, 맨 오른쪽 도시 주유비를 pop한 뒤

그 배열 값중 min을 이용해 최솟값을 찾아 남은 거리와 곱하는 방식을 구현했다.

하지만.... 왜인지는 아직 모르겠으나 틀렸다고 뜬다. (예시는 맞는걸 확인했지만 실제 테스트 케이스는 무궁무진하니까)

어떤 예외가 있는지는 더 생각해봐야할 것 같다.

시험이 끝나고 더 생각해보고 반례 찾으면 아래에 추가적으로 작성해야지

아래 그림은 실패한 코드.

그래서 이번엔 주유를 하고 도시를 지날 때마다 최솟값을 비교하고 갱신하는 알고리즘을 구현했다.

여기서도 for문 내에서 total 값을 조건문 밖으로 빼내서 쓰면 틀렸다고 떴다.

이 사례랑 위의 알고리즘이 오답이 된 원인이 아마 동일할 것으로 예측된다.