[알고리즘][Python] 백준(BOJ) 13305 주유소_파이썬

 

13305 주유소    www.acmicpc.net/problem/13305

13305번: 주유소

 

 

문제 풀기 전 공부할 것 : 그리디 알고리즘

 

 

 

 

 

 

 

풀이 1

<내용>

• 도시의 개수와 도로의 길이, 주유소의 리터당 가격을 n, roads, costs에 입력받는다.
• 두 번째 도시로 가기 위해서 무조건 첫 번째에서 주유를 해야 한다.
  • 첫 번째에서 두 번째 도시로 가는 도로의 길이 * 첫 번째 도시에서의 주유소의 리터당 가격을 더한다.
• for문을 돌면서 지금까지 주유 가격보다 이번 도시에서의 가격이 작으면 지금까지 왔던 거리 * 가장 작았던 주유 가격을 곱해서 결과에 더해준다.
• 그리고 주유 가격을 제일 작은 가격으로 바꾼다.
• 마지막 도로에서 넘어갈 때 가격을 계산한다.

 

 

<코드>

n = int(input())
roads = list(map(int, input().split()))
costs = list(map(int, input().split()))

res = roads[0] * costs[0]
m = costs[0]
dist = 0
for i in range(1, n-1):
    if costs[i] < m:
        res += m*dist
        dist = roads[i]
        m = costs[i]
    else:
        dist += roads[i]
        
    if i == n-2:
        res += m*dist
print(res)

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 위와 전체적인 흐름은 같지만 더 간단한 풀이이다.
• for문을 돌면서 매번 res에 더해주는 것이다.
• 지금까지 지났던 주유소의 리터당 가격 중 가장 작은 값으로 도로를 이동한다고 생각하면 된다.
• 따라서 주유소 가격은 지금까지의 주유소 가격보다 작을 때 갱신된다.

 

 

<코드>

n = int(input())
roads = list(map(int, input().split()))
costs = list(map(int, input().split()))

res = 0
m = costs[0]
for i in range(n-1):
    if costs[i] < m:
        m = costs[i]
    res += m * roads[i]
    
print(res)