일단 코드는 다음과 같이 하면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
cityNum = int(input())
roads = list(map(int, input().split()))
price = list(map(int, input().split()))
minPrice = price[0] # 주유소 리터당 가격이 가장 작은 것
res = 0
# 마지막 도시(=도착지)의 L는 따질 필요가 없다.(=n-1 도시의 수 만큼 반복)
for i in range(cityNum-1):
if minPrice <= price[i]:
res = res + (minPrice * roads[i])
elif minPrice > price[i]:
minPrice = price[i]
res = res + (minPrice * roads[i])
print(res)
|
cs |
전략 설명
[예시 그림]
3 2 1
A ---> B ---> C ---> D
5L 2L 3L 1L
1. 첫 번째 도시에서는 무조건 다음 도시까지의 거리만큼을 주유해야 한다.
따라서, 가장 작은 주유소 리터당 가격(=minPrice)를 첫 번째 도시에서 가지게 된다.
[예시] A도시에서 주유를 하면 무조건 5L 를 3만큼 가야 한다.
따라서, minPrice = 5로 시작해서, res=5L*3이 된다.
2. 다음 도시부터는 도시에서 가지는 리터당 주유소 가격이 가장 작은 값으로 계속 그다음 도시까지의 거리만큼 넣으면 된다.
[예시] B도시에서 주유를 하면 이전도시(A도시)보다 주유소 리터당 가격이 작으므로 (5L > 2L), minPrice = 2L로 바뀌고,
다음 도시(C도시)까지의 거리만큼 이동해서 res = res + (2L * 2) 가 된다.
3. 마지막 도시에 도착할 때까지 2번(minPrice와 res 업데이트) 반복
[예시] C도시에서 B도시의 리터당 주유소 가격이 더 크므로 (2L < 3L),
더 작은 가격을 가졌던 이전 도시(B도시)에서 C에서 D로 가는 거리만큼 더 넣어야 최소비용이 들어감을 알 수 있다.
따라서, res = res + (2L * 1)이 된다.
최종 값은 (5L*3) + (2L * 2) + (2L * 1) 가 된다.
반성
전략 자체에 대해서 떠오르는데 어려웠다...
문제 출처: https://www.acmicpc.net/problem/13305
13305번: 주유소
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1
www.acmicpc.net
'코딩 문제풀이 및 연습 > Python 연습' 카테고리의 다른 글
| [백준] 6768_Don’t pass me the ball! 파이썬 (combination함수) (0) | 2021.10.09 |
|---|---|
| [백준] 11399_ATM 파이썬 (그리디 알고리즘 / 정렬) (0) | 2021.10.07 |
| [백준] 7568_덩치 파이썬 (0) | 2021.09.27 |
| [백준] 2798_블랙잭 파이썬 (combination함수 vs 3중for문) (0) | 2021.09.26 |
| [백준] 5532_방학 숙제 파이썬 (if-else vs ceil함수) (0) | 2021.09.22 |