〔백준/파이썬〕13305번 주유소

 

출처

13305번: 주유소

 

---

 

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

 

---

 

예제

# 입력
4
2 3 1
5 2 4 1

# 출력
18

 

---

 

아이디어

• 주유 비용이 가장 저렴한 도시(A)에서 최종 목적지까지 필요한 기름 몽땅 채우기
• A에 도착하기 전에는 개중에서 가장 저렴한 도시(B)에서 A까지 필요한 기름 몽땅 채우기
• B에 도착하기 전에는 ... 반복
• 예시: 도시별 주유 가격과 거리가 3 - (1) - 4 - (1) - 1 - (1) - 2 - (1) - 3 이라면, 첫 번째 도시에서 주유(3 * 2), 세 번째 도시에서 주유(1 * 2)

 

---

 

풀이 - (1) 재귀함수 (58점 부분 통과)

def	get_minimum_sum(end, sum) :
	if end == 0 :
		return sum
	# 최소 비용이었던 도시 이전에 방문하는 도시들 사이에서의 최소 비용 탐색
	cheapest = min(prices[:end])
	pos = prices.index(cheapest)
	distance = 0
	for i in range(pos, end) :
		distance += distances[i]
	sum += cheapest * distance
	sum = get_minimum_sum(pos, sum)
	return sum

# 총 도시 수, 도시간 거리, 도시별 주유 가격
cnt = int(input())
distances = list(map(int, input().split()))
# 마지막 도시에선 실제로 이동하지 않지만 계산상 편리를 위해 0 추가
distances.append(0)
prices = list(map(int, input().split()))

# 가장 저렴하게 주유할 경우의 총 비용
sum = 0
# 재귀 함수에 넘겨줄 인자를 리스트의 마지막 인덱스 + 1 로 초기화
pos = len(prices)
sum = get_minimum_sum(pos, sum)
print(sum)

• 가장 저렴한 도시의 인덱스(pos)를 찾아서 end - 1 까지 모두 주유한다
• 여기서 찾은 pos 를 다음 재귀 함수의 end 매개변수로 넘겨준다
• 그러면 호출된 재귀 함수는 가장 저렴한 도시의 인덱스 직전까지 다시 탐색하여 그 중에서 가장 저렴한 도시를 찾고 위의 과정을 반복한다
• 3 - (1) - 4 - (1) - 1 - (1) - 2 - (1) - 3 으로 예를 들면, 가장 저렴한 도시의 가격이 1 이므로 마지막 도시까지 주유하면 1*2
• 가격이 1인 도시에 도착하기까지도 기름이 필요하므로 그 이전 도시 중에 가장 저렴한 것을 찾으면 3 이므로 3 * 2
• 이것을 모두 더하면 모든 도시를 여행하는 데에 드는 최소 비용은 2 + 6 = 8 

 

---

 

풀이 - (2) 반복문

# 총 도시 수, 도시간 거리, 도시별 주유 가격
cnt = int(input())
distances = list(map(int, input().split()))
prices = list(map(int, input().split()))

# 가장 저렴하게 주유할 경우의 총 비용
sum = 0
# 지금까지 탐색한 도시 중에 최소 비용
min = prices[0]
for i in range(len(prices) - 1) :
	if prices[i] < min :
		min = prices[i]
	sum += min * distances[i]
print(sum)

• 첫번째 도시부터 순차적으로 탐색하여 인덱스가 하나 증가할 때마다 sum 을 증가시키는 방식
• 맨 처음 탐색한 도시는 당연히 아직까지 탐색한 도시가 하나 밖에 없으므로 가장 저렴, 3 * 1 을 더한다
• 두 번째 탐색한 도시는 첫 번째 도시보다 비싸므로 (3 < 4) 첫 번째 도시에서 모두 주유하면 3 * 1
• 세 번째 탐색한 도시의 가격은 3보다 저렴하므로 min 을 1로 업데이트, 1 * 1
• 네 번째 탐색한 도시의 가격은 1보다 비싸므로 세 번째 도시에서 모두 주유하면 1 * 1

 

---

 

풀이 - (3) zip() 활용

# 총 도시 수, 도시간 거리, 도시별 주유 가격
cnt = int(input())
distances = list(map(int, input().split()))
prices = list(map(int, input().split()))
# 마지막 도시의 주유 가격은 필요 없음
prices.pop()

# 가장 저렴하게 주유할 경우의 총 비용
sum = 0
# 지금까지 탐색한 도시 중에 최소 비용
min = prices[0]
for price, distance in zip(prices, distances) :
	if price < min :
		min = price
	sum += min * distance
print(sum)

• 두 번째 풀이와 동일하나 for 문에서 zip() 메서드를 활용해보았다
• zip()은 여러 이터레이터를 병렬로 순회하는 효율적인 방법을 제공한다
• zip 제너레이터는 각 이터레이터로부터 다음 값을 담은 튜플을 얻어온다
• 위의 예시를 가져오자면 첫 번째 튜플은 (3, 1)이 되고 두 번째 튜플은 (4, 1)이 되는 식이다

주의: 서로 길이가 다른 이터레이터를 사용하면 zip 은 그 결과를 조용히 잘라내기 때문에 기대와 다른 결과가 나오게 된다. 반드시 서로 길이가 같은 이터레이터를 사용하자! 위의 코드에서는 prices 의 마지막 요소가 어차피 필요 없기
때문에 pop() 으로 제거해주었으므로 prices 와 distances 의 길이가 같다.

 

---

 

풀이 - (4) enumerate() 활용

# 총 도시 수, 도시간 거리, 도시별 주유 가격
cnt = int(input())
distances = list(map(int, input().split()))
prices = list(map(int, input().split()))
# 마지막 도시의 주유 가격은 필요 없음
prices.pop()

# 가장 저렴하게 주유할 경우의 총 비용
sum = 0
# 지금까지 탐색한 도시 중에 최소 비용
min = prices[0]
for i, price in enumerate(prices) :
	if price < min :
 		min = price
 	sum += min * distances[i]
print(sum)

• 2, 3번째 풀이와 동일하나 enumerate() 를 사용해본 풀이 방식이다
• enumerate() 제너레이터는 이터레이터에서 루프 인덱스와 값을 한 쌍으로 가져와 넘겨준다
• 2번 풀이에서 사용한 방법은 for i in range(len(prices) - 1) : 처럼 인덱스를 구해서 prices[i] 처럼 접근하느라 읽기에 복잡함이 있는데, enumerate()를 사용하면 코드가 간결해진다
• 다만 3번 풀이에서 사용한 zip()이 이번 문제에서는 더 깔끔하기 때문에 베스트는 3번 풀이

 

---

 

노트

• 리스트 컴프리헨션을 사용한 방법도 있었는데 너무 복잡해보여서 제출하지 않음
• prices = [(i, price) for i, price in enumerate(prices) if i < len(prices) - 1] 를 사용하여 prices.pop() 을 대신해서 prices 의 마지막 요소를 슬라이싱 해보았다

파이썬 zip( ) 함수_ 길이가 같은 리스트 등의 요소를 묶어주는 함수 (Python)

[Python] 파이썬 enumerate 함수 사용법/예제

 

1) 리스트 컴프리헨션