백준13305 파이썬(그리디)

 

   

# 주유소

n = int(input())
dis = list(map(int,input().split()))
oil = list(map(int,input().split()))

res = 0
i = 0
j = 0

tot_dis = sum(dis) 

while tot_dis != 0:
    if oil[i] >= oil[i+1]:
        res += oil[i]*dis[j]
        tot_dis -= dis[i]
        i += 1
        j += 1

    else:
        res += oil[i]*dis[j]
        tot_dis -= dis[j]
        j += 1

print(res)

 

일단 입력조건들을 만족시킨 후

기름값을 비교하여 문제를 풀었다.

지금 도시에서의 기름값과 다음 도시에서의 기름값중 지금이 기름이 더 비싸면 다음 도시에 갈 만큼만 기름을 넣어주고

그렇지 않다면 그 다음 도시에서도 또 예전 기름가격으로 주유할 수 있도록 생각해보았다.

 

*그리디(Greedy)

이번 문제에서 그리디 개념은

가장 싼 기름을 최대한으로 주유할 수 있도록 알고리즘을 구현하는 부분에서 적용된것 같다.