[백준] #13305 주유소

백준 #13305 Level : 💣

---

✍Logic

문제는 생각보다 간단하다.

기름 가격이 가장 작은 도시에서 최대한 많이 사고, 그 외의 도시에서는 당장 이동하는데 필요한 만큼만 사주면 되는 문제였고, 아래와 같은 솔루션으로 문제를 해결했다.

[1] 주유소를 순차적으로 이동하면서 이동후의 기름값이 현재 기름값보다 크거나 같으면 계속 이동하고, 작으면 멈춘다.  

[2] 이동이 멈추면, 출력값에 '이동한 거리 * 현재 기름 가격' 만큼 더해준다.  

---

💻Code

if __name__ == '__main__':
    n = int(input())                        # n: 도시 개수
    dis = list(map(int, input().split()))   # dis: 도시간 거리
    oil = list(map(int, input().split()))   # oil: 주유소 가격
    ans = i = j = 0                         # i: oil의 idx, j: dis의 idx

    while i < n - 1:
        min_oil = oil[i]                    # min_oil: 현재 주유소 가격
        cnt = 1                             # cnt: 이동 횟수
        # [1]
        while i+cnt < n and min_oil <= oil[i+cnt]: cnt += 1
        # [2]
        ans += min_oil * sum(dis[j:j+cnt])
        j += cnt
        i += cnt

    print(ans)

🙋‍♀️REF

문제를 다 풀고 깨닳은 점은 ‘그리디 알고리즘’으로 더 쉽게 해결할 수 있다는 것이다.

‘그리디 알고리즘’은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불린다.

미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이며, 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이다.

‘그리디 알고리즘’을 적용하여 문제를 다시 풀어보았고, 시간복잡도도 위의 코드 보다 더 개선하였다.

[1] 첫번째 주유소의 기름값을 가장 싼 기름값로 저장한다.  

[2] 주유소를 1칸씩 이동하면서,   

    (1) 이동후의 기름값이 현재 기름값보다 크거나 같으면 : (1칸 거리 * 현재 주유소 가격) 더해줌  

    (2) 작으면 : 이동후의 기름값을 가장 싼 기름값으로 저장하고 더해준다.   <br>

if __name__ == '__main__':
    n = int(input())                        # n: 도시 개수
    dis = list(map(int, input().split()))   # dis: 도시간 거리
    oil = list(map(int, input().split()))   # oil: 주유소 가격

    # [1]
    min_oil = oil[0]
    ans = dis[0] * min_oil

    # [2] 
    for i in range(1, n-1):
        if min_oil > oil[i]:
            min_oil = oil[i]
        ans += min_oil * dis[i]

    print(ans)