백준 13305 주유소

주유소 (백준 13305)

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

요점은 ‘다음 도시’의 기름값이 ‘현재 도시’보다 크냐는 것이다
그 경우는 ‘현재 도시’에서 그 다음 도시에서 갈만큼 기름을 채우면 되므로
다음 도시의 기름값을 현재 도시의 기름값으로 덮어씌우는 방식으로 진행하였다

해당하는 판단을 각 도시마다 진행하기에 ‘최적 부분 구조’를 가지며,
또한 각 도시에서 최소한의 기름값을 사용하는 것이
가장 왼쪽에서 가장 오른쪽 도시까지 가는 최소 기름값에 부합하기에
‘탐욕 선택 속성’을 만족한다고 할 수 있다

Code

import sys
inp = sys.stdin.readline

num = int(inp().strip()) # 도시 수

edges = list(map(int,inp().split()))        # 도시간 거리
oilValues = list(map(int,inp().split()))    # 해당 도시에서 기름값

# 그리디
# 다음 도시의 기름값이 현재 도시보다 크다면 현재 도시에서 채워감

sumValues = 0

for i in range(num - 1): # 어차피 마지막 도시의 기름값은 의미없으므로
    if oilValues[i] < oilValues[i+1]:
        oilValues[i+1] = oilValues[i]
    
    sumValues += (oilValues[i]*edges[i])

print(sumValues)

해결 아이디어

1. 다음 도시로 가는 비용이 현재 도시보다 작다면,
   현재 도시에서 채워가는 것이 좋으므로
   다음 기름값과 비교하여 덮어씌울지 여부를 판단한다
2. 해당 요소를 비교하는 것은 ‘각 도시’에서 이루어지므로
   for을 돌려 비교하며, 정해진 기름값과 갈 거리를 곱하여 더한다
   
3. 반복문을 다 돈 뒤, 출력한다