[백준 파이썬] # 13305 주유소

Siver IV

# 13305 주유소

그리디 알고리즘

 

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

13305번: 주유소

 

 

풀이

N = int(input())
D = list(map(int, input().split()))  # Distance
P = list(map(int, input().split()))  # Price
C = 0                                # Cost
M = 1000000001                       # Minimum Distance

C += D[0]*P[0]    # D, P의 크기와 관계없는 가장 첫 비용을 계산

# 가격이 가장 적은 지점을 찾기 위해 M을 활용
# M 보다 작은 P 값을 찾을 때 그 값을 M으로 대체
# 새로운 도시에서 D 만큼의 거리를 가기 위한 비용을 비교 : 가격은 M or P[i]

for i in range(1, N-1):    
    if M > P[i-1]:
        M = P[i-1]
    C += min(D[i]*M, D[i]*P[i])

print(C)

 

• for 문이 진행될 때 비교해야 하는 변수 M을 설정하는 것이 핵심인 듯 하다
• 값 도출에 필요한 요소들이 무엇인지 잘 살펴보고, for문이 진행될 때 값이 어떻게 변하는 지 생각해봐야 한다 (자주 놓쳐서 애먹는 부분!)