[백준] 13305번 주유소 파이썬(그리디 알고리즘)

https://www.acmicpc.net/problem/13305

13305번: 주유소

1. 문제 설명

도시 개수, 도시 별 1리터 당 기름 가격, 도시에서 도시 사이의 거리를 입력받아 주유비의 최솟값을 구하는 문제다.

 

2. 풀이

첫 번째 시도(17점) 

1. 어차피 마지막 도시에서는 더 가지 않으니 가격을 생각하지 않았다.

2. price의 최솟값을 구해 그 도시부터 마지막 도시까지 가는 거리를 더했다.

3. 최솟값 도시가 오기 전까지는 반복문을 돌면서 다음으로 갈 도시의 거리와 현재 도시 가격을 더했다.

A=int(input())
distance = list(map(int, input().split()))
price = list(map(int, input().split()))
price = price[0:-1] #마지막 도시는 어차피 더 갈 곳이 없으니 제외

min_price = price.index(min(price)) 
answer = price[min_price]*sum(distance[min_price:]) 
for i in range(min_price):
  answer += price[i]*distance[i]
print(answer)

 

그런데 이렇게 푸니 서브태스크 1번만 통과했다.

 

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

min_price = price[0] #최소 가격을 첫 번째 인덱스로 설정
answer = 0

for i in range(A-1): #마지막 인덱스 제외하고 반복문 수행
  if min_price>price[i]: #현재 인덱스값이 최솟값보다 작으면 min_price 바꿔줌
    min_price = price[i]
  answer+=min_price*distance[i] #현재 인덱스 거리값과 최솟값을 곱해줌
print(answer)

 

위 로직으로 바꾸어주니 100점을 맞을 수 있었다. 

 

1. 처음에는 무조건 충전을 해야 하니 최소 가격을 첫 번째 인덱스로 설정해준다.

2. for문을 돌면서 현재 최솟값보다 현재 인덱스 값이 더 작으면 최솟값을 바꿔준다.

3. 최솟값과 거리를 곱한다.

 

처음에는 최솟값을 구하고, 최솟갑 인덱스부터 끝까지의 거리를 곱한 후, 앞의 인덱스 값들을 계산해주었고, 두 번째는 앞에서부터 최솟값을 찾아가면서 값을 구해주는 방식이다.

 

가격이 5,2,3,4,1 이런 식으로 있을 때, 처음에는 가격 5로 첫 번째 거리만큼을 충전하고, for문을 돌면서 최솟값이 2로 바뀐다. 이후 도시들을 갈 때 최솟값이 유지되기 때문에 가장 싼 가격으로 충전을 할 수 있게 된다.