[백준] 13305번: 주유소

박정훈·2022년 4월 7일
0

코테 문제 모음

목록 보기
21/34

주유소

문제

N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다고 하자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다.

처음 출발할 때는 자동차에 기름이 없기 때문에 반드시 첫 도시에서 기름을 넣고 출발한다. 1km를 갈 때마다 1L의 기름을 사용한다.

각 도시에는 단 하나의 주유소가 있으며, 도시마다 주유소의 리터당 가격은 다를 수 있다.

왼쪽에서 오른쪽 끝까지 이동할 때 최소 비용을 구하라.

어떻게 풀면 좋을까?

일단 첫 도시에서 최소 다음도시까지는 충전한다. 아무리 비싸도 다음 도시까지는 가야한다.
또한 첫 도시의 기름 가격을 최소라고 가정해 놓는다. 다음 도시부터 기름 가격을 비교하면서 더 낮은 가격의 기름을 찾는다면, 최소 오일의 가격을 바꿔주고, 거리 * 기름가격을 해서 정답에 누적 시켜주면 될거 같다.

풀이

N = int(input())

roads = list(map(int, input().split()))
oil = list(map(int, input().split()))
# 첫 도시에서 기름 충전하고 시작~
price = roads[0] * oil[0]
min_price = oil[0]
# 두번째 도시부터 시작. N-1은 도로는 도시보다 하나 적으니까
for i in range(1, N-1):
	# 더 낮은 가격의 기름 발견!
    if oil[i] < min_price:
        min_price = oil[i]
    price += roads[i] * min_price

print(price)

코딩 해 보기 전에 어떻게 풀지 생각할 때, 아니... 어떻게 내 기름 가격이 최소인지 알고 미리 주유를 다 해놓지? 했었다. 마치 진짜 차타고 가는거마냥 생각을 해 버려서...
최소치만 저장 해 놓으면 다음 주유소 때 가격이 바뀌지 않으면 그냥 저장해 놨던 최소치로 계산하면 된다. 진짜 차 타고 가는거였으면 미리 주유를 했어야 겠지만...

profile
그냥 개인적으로 공부한 글들에 불과

0개의 댓글