13305번 주유소

문제

13305번: 주유소

 

나의 풀이

# 투포인터 한개는 left 나의 위치, right는 나보다 작은 노드의 위치 
# right 노드와의 거리까지 주유를 한다. 
# right가 left의 가격을 비교하고 더 작은 값이 나올 때 까지 이동

n = int(input())
distance_lst = list(map(int, input().split()))
price_lst = list(map(int, input().split()))

answer = 0

left = 0
right = left + 1
while right != len(price_lst):
    while price_lst[left] <= price_lst[right]:
        right += 1
        if right == len(price_lst) - 1:
            break

    for i in range(left, right):
        answer += distance_lst[i] * price_lst[left]
        
    left = right
    right = left + 1

print(answer)

1) 투포인터를 활용해서 왼쪽 오른쪽 지점으로 나눈다. 왼쪽 지점은 현재 내가 위치한 지점, 오른쪽은 현재 내가 위치한 주유소보다 가장 가까이 있으면서 주유비가 적은 위치

 

2) 왼쪽 지점과 오른쪽 지점의 차이만큼 주유를 채운다.

 

3) 주유 후 왼쪽 포인터와 오른쪽 포인터 업데이트  

 

4) 오른쪽 포인터가 끝에 도달할때까지 해당 구문 반복