[백준] 13305번 - 주유소 (그리디) - 결과 포함

www.acmicpc.net/problem/13305

13305번: 주유소

문제를 읽으면 입력도 많고 굉장히 복잡해 보이는 문제이지만 차근차근 생각해보니 간단한 문제였다.

 

거리와 기름의 가격을 생각해서 최소한의 비용으로 이동하는 문제인데 그리디 알고리즘에 알맞은 문제라고 생각했다.

왜냐하면 미래에 대해 걱정하지 말고 지금 현 상황에 가장 적절한 해법을 찾으면 되기 때문이다.

 

최소 비용이 되는 방법은

1) 다음 도시의 기름 가격을 본다.

2) 지금 도시보다 다음 도시의 가격이 싸면 다음 도시까지 필수로 필요한 만큼만 주유하고 이동한다.

3) 만약 다음 도시가 싸지 않다면 그 도시까지 가는 기름을 현재 도시에서 주유하고 이동하지 않는다.

 

현재 내가 있는 도시와 내가 가야하는 도시들의 가격을 비교하면서 더 싼 곳을 찾아 가는 방법이다.

이를 위해서 나는 두 개의 인덱스를 이용했다.

하나는 나의 현재 위치를 나타내는 인덱스이고,

다른 하나는 가격을 비교할 다음 도시의 위치를 나타내는 인덱스이다.

가격 비교 -> 이동 여부 결정 -> 기름 가격 계산 -> 결과 저장 순서이다.

 

주의할 점은 마지막의 도시가 가격이 낮아도 마지막 도시에서 주유할 일은 없기 때문에

마지막 도시에 대한 예외처리를 해주어야 한다.

 

[전체 소스 코드]

n = int(input())
distance = list(map(int, input().split()))
price = list(map(int, input().split()))

result = 0
curCity = 0
diffCity = 1

while diffCity < n:
    if price[diffCity] < price[curCity] and diffCity != n - 1:
        result += (distance[diffCity - 1] * price[curCity])
        curCity = diffCity
        diffCity += 1
    else:
        result += (distance[diffCity - 1] * price[curCity])
        diffCity += 1

print(result)