백준 문제풀이 - 13305 번

링크 -> https://www.acmicpc.net/problem/13305

1. 요약 및 풀이방법

처음 도시에서 마지막 도시까지 이동할 때, 기름값을 최소로 하여 가는 경우를 구하는 문제입니다.

앞에서 가능한 저렴한 가격으로 기름을 넣고,
이후에 더 저렴한 가격이 나오면 이후에는 그 가격으로 기름을 넣어야 합니다.

따라서 현재 도시의 기름값이 최소값 min_price 보다 가격이 높다면,
min_price로 바꿔버립니다.

예를 들어 각 도시의 기름값이 순서대로
5 6 6 4 3 1 2 5 일 때,
5 5 5 4 3 1 1 1 식으로 바꾸면,
매번 최적의 가격으로 다음 도시까지 가는 기름만 채우는 꼴이 됩니다.

이렇게 각 도시의 oil_price를 변경 후, distance와 곱하고 모두 더하여 해결합니다.

2. Code

import sys

def main():
    N = int(input())
    distance = list(map(int, sys.stdin.readline().rstrip().split()))
    oil_price = list(map(int, sys.stdin.readline().rstrip().split()))

    min_price = oil_price[0]
    for idx, price in enumerate(oil_price):
        min_price = min(min_price, price)
        oil_price[idx] = min_price

    total = sum(map(lambda x, y: x*y, distance, oil_price[:-1]))
    print(total)


if __name__ == "__main__":
    main()

3. 학습 내용

처음에는 뒤에서부터 최적의 가격으로 기름을 넣는 방식으로 풀었습니다.
이렇게 거꾸로 하게되면 앞에서 최솟값이 나온 경우를 해결 할 수 없습니다.

두 리스트의 값을 각각 곱하기 위해 map, lambda 함수를 이용해 간단히 구현하였습니다.

4. 결과