sm 기술 블로그
150. 13305(주유소) - 파이썬 본문
import sys
input = sys.stdin.readline
N = int(input())
road = list(map(int, input().split()))
city = list(map(int, input().split()))
result = 0
start = 0
for i in range(1, len(city)):
if (i == len(city)-1):
for j in range(start, len(road)):
result += road[j] * city[start]
elif (city[start] > city[i]):
for j in range(start, i):
result += road[j] * city[start]
start = i
else:
continue
print(result)
문제요약
왼쪽 도시부터 오른쪽 도시까지 최소의 주유비용으로 가시오
설명
다음과 같이 원안에는 가스비용 선 위에는 도로 길이라고 하자.
현재 두번째 도시가 첫번째 도시보다 주유 비용이 싸다.
때문에 일단 두번째 도시로 이동하기 위해서 5*2의 비용을 지불하고 두번째 도시로 넘어가야 한다.
하지만 세번째 도시는 두번째 도시보다 가격이 비싸다.
때문에 두번째 도시에서 네번째 도시까지 갈 수 있게 주유한다면 최소의 비용으로 도착이 가능하다.
따라서
만약 비교 도중에 주유비가 더 적은 도시를 만난다면, 주유비가 최소라고 생각했던 부분을 기점으로 더 적은 부분이 도달 할 수 있을 정도 까지 주유를 하고 더 적은 쪽에서 부터 다시 주행을 시작하면 된다.
다시 예를 들면
result = 0
start = 0
결과와 시작부분을 0으로 초기화 한다.
시작 부분은 지금까지 최소 부분을 담당한다.
for i in range(1, len(city)):
if (i == len(city)-1):
for j in range(start, len(road)):
result += road[j] * city[start]
elif (city[start] > city[i]):
for j in range(start, i):
result += road[j] * city[start]
start = i
else:
continue
최소 주유비를 구하는 로직이다.
먼저 elif 부분 부터 설명 하겠다.
elif (city[start] > city[i]):
for j in range(start, i):
result += road[j] * city[start]
start = i
지금까지 최소 비용(start) > 현재 비용 이라면 즉, 현재 비용이 더 낮다면,
start 인덱스 부터 현재 비용인덱스 전까지 도시 * 로드를 진행한다.
예를들어
입력이
7
3 4 2 2 4 5
8 9 5 4 2 7 1
다음과 같다면
지금까지 최소비용(start)는 8이고, 현재 최소 비용은 5이다.
따라서 8*3 + 8*4 를 진행한다.
그리고 지금까지 최소 비용을 현재 최소 비용의 인덱스로 저장한다.
if (i == len(city)-1):
for j in range(start, len(road)):
result += road[j] * city[start]
마지막 도시에 도달한 경우이다.(배열은 0부터 시작이기 때문에 길이 - 1이 마지막 도시이다.)
그러면 더이상 나아갈 곳이 없으니 지금까지 최소비용(start)을 가지고 진행되지 않은 도로의 값들을 계산해준다.
else:
continue
continue를 통해서 현재 가지고 있는 비용이 최소이면 다음으로 넘어간다.
'문제 > 백준_파이썬' 카테고리의 다른 글
152. 10773(제로) - 파이썬 (0) | 2022.07.20 |
---|---|
151. 10828(스택) - 파이썬 (0) | 2022.07.20 |
149. 1541(잃어버린 괄호) - 파이썬 (0) | 2022.07.18 |
148. 11399(ATM) - 파이썬 (0) | 2022.07.18 |
147. 1931(회의실 배정) - 파이썬 (0) | 2022.07.17 |