[백준] 13305 주유소

iamjinseo·2022년 8월 5일

그리디 백준

문제풀이-Python

목록 보기

33/134

문제

동그라미는 1만큼의 거리를 가는데 드는 비용이고 직선은 거리이다.
제일 오른쪽 도시로 가기 위한 최소 비용 구하기

입출력

시도

1

리터당 기름값이 가장 낮은 곳에서 다 사기
1. 기름값 중에서 최저값 찾기
2. 일단 첫번째 장소에서 다음 장소로 건너갈 수 있을 만큼의 기름 사기
3-1. 다음 장소가 최저값 장소면 거기서 남은 거리만큼 다 사기
3-2. 다음 장소가 최저값 장소가 아니면 그 다음 장소로 건너갈 만큼의 기름 사기

일단 만점이 아닌 17점 맞음
근데 이 생각에는 허점이 있다. 바로 첫번째 장소가 최저가면 어떡할 것인가!!!!
그래서 17점인가?

2

리터당 기름값이 가장 낮은 곳에서 다 사기
1. 기름값 중에서 최저값 찾기
2-1. 현재 장소가 최저값 장소면 거기서 남은 거리만큼 다 사기
2-2. 현재 장소가 최저값 장소가 아니면 그 다음 장소로 건너갈 만큼의 기름 사기

근데 이렇게 했더니 또 17점 맞음
하

3

반례를 알아냈는데
4
1 1 1
2 3 1 4 입력하면 답이 5로 나와야된다고 한다. 근데 나는 6이 나옴
아마 가격이 2일때 사고 3일때 사고 그래서 그런듯 ㅠ

그러면 1에 도달하기 위해 2에서 1까지만큼을 사야되나?

기름값 중에서 최저값 찾기
2-1. 현재 장소가 최저값 장소면 거기서 남은 거리만큼 다 사기
2-2. 현재 장소의 가격이 최저값은 아니지만 다음 장소보다 낮으면 다음 장소의 거리만큼 사기
2-3. 현재 장소가 최저값 장소가 아니면 그 다음 장소로 건너갈 만큼의 기름 사기

근데 이것도 17점임!!
이게 정답이 아닐 것 같긴 했다.
예를들어 비용이 5 - 3 - 5 - 4 - 5 - 2 - 5 같이 생겼을 때 최소값 장소 2에 도달할 때까지 3의 비용으로 계속 달리면 되는데, 내 알고리즘에서는 3에서 5까지밖에 못 달린다.

import sys
n = int(sys.stdin.readline())
dis = list(map(int, sys.stdin.readline().split()))
charge = list(map(int, sys.stdin.readline().split()))
result = 0 #드는 돈

low = min(charge[:len(charge)-1]) #마지막 장소 기름값 제외한 최저 기름값
i=0
while True: #마지막에서 그 앞의 장소까지 여행하기
    if charge[i] == low: # 최저값일때 한방에 가기
        result += charge[i]*(sum(dis[i:])) # 남은 거리만큼의 기름 사기
        break
    elif charge[i] < charge[i+1] : #다음 장소보다 가격 낮을 때
        result += charge[i]*(dis[i]+dis[i+1]) # 두 거리를 더 갈만큼 사기
        # 예를들어 거리는 1 1 1이고 가격이 2 3 1 4면 2에서 3-1만큼의 거리도 같이 사는거임
        i+=2
    else: # 그냥 지나가기
        result += charge[i]*dis[i]
        i+=1
print(result)

4

결국!!!
구글링을 하기로 했음 (참고: https://alpyrithm.tistory.com/134)

n = int(input())
roads = list(map(int, input().split())) 
costs = list(map(int, input().split())) 

res = 0 
m = costs[0] # 이동 비용
for i in range(n-1):
    if costs[i] < m: # 각 비용을 순회하며 최소값이라 여겨지는 가격보다 작으면
        m  = costs[i] #현재 비용을 최소값으로 변경
    res += m * roads[i] # 최소값 * 거리
    
print(res)