[baekjoon] 백준 13305번(파이썬): 주유소

문제

13305번: 주유소

- 어떤 나라에 N개의 도시가 있다.

- 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다.

- 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

- 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다.

- 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다.

- 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다.

- 각 도시에는 단 하나의 주유소가 있으며, 도시마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

- 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다.

- 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 

- 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다.

- 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1 이상 1,000,000,000 이하의 자연수이다.

- 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

- 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 구하는 문제이다. 

알고리즘

- 도시의 개수를 입력받는다.

- 도로의 길이를 입력받는다.

- 리터당 가격을 입력받는다.

- 처음 출발할 때 자동차에는 기름이 없기때문에 처음 도시에서 기름을 넣고 출발한다.

- 도시의 기름을 비교하고 이전 도시에 기름이 더 싸면 그다음 도시까지 갈 수 있을 만큼만 기름을 산다.

- 다음 도시에 기름이 더 싼 경우에는 그 다음 도시까지 갈 수 있을 만큼만 기름을 산다.

- 비교할 도시의 기름값을 제일 싼 도시의 기름값으로 바꿔준다.

코드

n = int(input())
l = list(map(int, input().split()))
o = list(map(int, input().split()))

# 제일 싼 기름을 파는 도시의 위치
a = 0
# 처음 출발할 때 자동차에는 기름이 없기때문에 처음 도시에서 기름을 넣고 출발한다.
result = o[0] * l[0]

for i in range(1, (n-1)):
    # 도시의 기름값을 비교
    # 이전 도시의 기름값이 더 싸면 이전 도시의 기름을 그다음 도시까지 갈 수 있을만큼만 산다.
    if o[a] <= o[i]:
        result += o[a] * l[i]
    # 다음 도시의 기름값이 더 싸면 다음 도시의 기름을 그다음도시까지 갈 수 있을만큼만 산다.
    else:
        result += o[i] * l[i]
        # 비교한 도시중에 제일 싼 기름을 파는 도시의 위치를 바꾼다.
        a = i
        
print(result)

github

junjange/CodingTest