Baekjoon #13305 - 주유소

목차

1. 문제

2. 입출력 예시

3. 문제 풀이

1. 문제

• 백준알고리즘 문제 - 13305번 주유소

2. 입출력 예시

입력 예시	출력 예시
4 2 3 1 5 2 4 1	18
4 3 3 4 1 1 1 1	10

3. 문제 풀이

문제에서 도시 간 이동거리와 도시 별 주유비에 대한 정보가 주어진다. 이 중 가장 마지막 도시는 도착지이며, 도착지에서 주유할 필요가 없기 때문에 주유비의 마지막 정보는 필요하지 않다. 또한, 도시가 2개일 경우 첫 번째 도시에서 주유를 하고 다음 도시로 이동해야 하므로, 별도의 비교는 할 필요가 없으며 첫 번째 도시의 주유비와 이동 거리를 곱하면 된다. 이 점을 참고하여 문제를 요약 후 순서로 나타내면 다음과 같다.

• 도시의 수(N)를 입력받는다.
• 도시 간 이동 거리(route)를 입력받는다.
• 각 도시의 주유비(price)를 입력받는다.
• 만약에 도시의 수가 2보다 작거나 2일 경우 주유비를 비교할 필요가 없으므로 도시 간 이동거리와 첫 번쨰 도시의 주유비를 곱한 값을 출력한다.
• 그 외의 경우는 현재 주유비(cost)를 첫 번째 도시의 주유비로 초기화하고, 총 비용(total)을 첫 번째 도시의 주유비에 첫 번째 도시에서 두 번째 도시까지의 이동 거리를 곱한 값으로 초기화한다.
• 도시 간 이동거리와 각 도시의 주유비 모두 두 번째 부터 반복하며 해당 도시의 주유비(p)가 현재 주유비보다 작을 경우 현재 주유비를 해당 도시의 주유비로 초기화한다. 반복을 수행할 때마다 총 비용에 현재 주유비와 도시 간 이동거리(r)을 곱한 값을 더한다. (입출력 예시 중 첫 번째 예시를 활용한 아래 표 참조)
• 반복이 종료되면 총 비용을 출력 후 프로그램을 종료한다.

반복횟수	도시의 주유비(p)	도시 간 이동거리(r)	현재 주유비(cost)	총 비용(total)
초기설정	-	-	5	10원 (5L/km × 2km)
1	2	3	2 (2 < 5)	16원 (10원 + 2L/km + 3km)
2	4	1	2 (4 > 2)	18원 (18원 + 2L/km + 1km)

입출력 예시 중 첫 번째 예시를 활용한 위의 표를 통해 알 수 있듯이 주유비 정보만 비교하면 매우 간단하게 해결할 수 있으며, 이를 구현한 코드는 아래와 같다. 이 코드는 메모리 44,216 KB, 시간 148 ms가 소요되었다.

N = int(input())
route = list(map(int, input().split()))
price = list(map(int, input().split()))[:-1]

if N <= 2:
    print(route[0] * price[0])

else:
    cost = price[0]
    total = cost * route[0]

    for (p, r) in zip(price[1:], route[1:]):
        if cost > p:
            cost = p
        total += cost * r

    print(total)