boj 13305 : 주유소

문제 주소: https://www.acmicpc.net/problem/13305

난이도: silver 4

1.문제설명

• 도시가 일자로 나열되어있다, 좌측에서 우측으로 이동해야한다.
• 도시에서 주유를 할수 있고, 도시마다 기름가격이 다르다
• 1km갈때마다 기름 1리터를 쓴다
• 도시마다 기름가격, 도시간의 거리가 주어질때
• 가장 왼쪽도시부터 오른쪽 도시까지 가는 최소 기름값은?

2.문제해결 아이디어.

• 특정도시 방문 -> 가격이 제일 저렴하다? -> 다 사버린다
• 제일 저렴한 가격 아님 -> 다음도시보다 비싸다? -> 다음도시 갈수있을 거리만큼만 삼
• 다음 도시보다 싸다 -> 자기보다 저렴한 가격의 도시 갈수있을만큼 산다

3.문제접근법

• 일단 내가 기름값이 가장 저렴한 도시에 있는지 확인해야하기 때문에,
  • 도시의 가격을 정렬해서 0번째 인덱스를 쓰던지
  • min(리스트) 해서 가장 싼 가격을 알아낸다.
• cur_loc이라는 변수에 현재 위치를 담아서
• cur_loc < n까지 while문을 돌릴것이다.
  • 내가 있는곳이 제일 싼 곳이라면
  • ans += sum([best_price * item for item in distance[cur_loc:]])
• 다음 도시가 지금 도시보다 저렴하면

  • ans += distance[cur_loc] * price[cur_loc]
            cur_loc += 1

• 현재 도시가 다음도시보다 저렴하면

  • smaller = find_smaller(cur_loc, price)
          ans += sum([price[cur_loc] * item for item in distance[cur_loc:smaller]])
          cur_loc = smaller

4.특별히 참고할 사항

• 현재 도시가 다음도시보다 저렴한 경우에 어디까지 갈만큼 사야하는지를 계산하는 부분이 인덱스를 생각해야해서
  까다로웠지만 어렵진 않다.

5.코드구현

n = int(input())
distance = list(map(int, input().split()))
price = list(map(int, input().split()))
best_price = min(price) #nlogn
ans = 0
cur_loc = 0

def find_smaller(cur_loc, price):
    _temp = cur_loc
    for _temp in range(cur_loc, n):
        if price[_temp] < price[cur_loc]:
            return _temp
#특정도시 방문 -> 가격이 제일 저렴하다? -> 다 사버린다
#제일 저렴한 가격 아님 -> 다음도시보다 비싸다? -> 거리만큼만 삼
#다음 도시보다 싸다 -> 자기보다 싼 가격 나올때까지 다 삼

while cur_loc < n:
    if price[cur_loc] == best_price:
        ans += sum([best_price * item for item in distance[cur_loc:]])
        break
    else:
        if price[cur_loc] >= price[cur_loc+1]:
            ans += distance[cur_loc] * price[cur_loc]
            cur_loc += 1
        else:
            smaller = find_smaller(cur_loc, price)
            ans += sum([price[cur_loc] * item for item in distance[cur_loc:smaller]])
            cur_loc = smaller

print(ans)