[Python] 백준 #13305- 주유소

문제

---

13305번: 주유소

코드

---

My answer

import sys
input=sys.stdin.readline

n=int(input())
k=list(map(int,input().split()))
cost=list(map(int,input().split()))
result=0

start=cost[0]
starti=0

for i in range(1,len(cost)):
    if(cost[i]<=start):
        result+=start*sum(k[starti:i])
        start=cost[i]
        starti=i
    else:
        if(i==len(cost)-1):
            result+=start*sum(k[starti:i+1])
print(result)
-----------------------------------------------------------------
import sys
input = sys.stdin.readline

n=int(input())
city=list(map(int,input().split()))
price=list(map(int,input().split()))

answer=0
j=0
for i in range(len(price)):
    if(i<j):continue
    for j in range(i+1,len(price)):
        if(price[i]>price[j]):
            break
    answer+=price[i]*sum(city[i:j])
print(answer)

Another answer

n=int(input())
d=list(map(int,input().split()))
p=list(map(int,input().split()))
s=0
k=p[0]
for i in range(n-1):
    if p[i]<k:
        k=p[i]
    s+=k*d[i]
print(s)

풀이

---

이 문제의 키 포인트는, 최적을 찾기 위해서는 현재 주요소에서 그것보다 싼 주유소가 나오기 전까지 갈 수 있는 기름을 넣어야 하는 것이다.

백준상으로 100점이 나오지 않는 경우는, 4 / 1 1 1 1 / 2 3 1 4 의 정답이 5가 나오지는 확인해보면 될 것이다.

나는 두가지 방법으로 풀었는데, 한 가지는 이중 반복문을 이용해서 현재 주유소보다 싼 주유소가 나올 때까지 찾고, 거기까지 갈 수 있는 거리를 곱하는 것 두번째 방법은 동일한 아이디어지만 이중 반복문으로 찾고, 곱하는게 아니라 최적의 가격을 k에 저장하면서 한단계씩 곱하는 것이다.