[백준] 13305번 : 주유소 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

https://www.acmicpc.net/problem/13305

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 전형적인 그리디 알고리즘 문제라고 볼 수 있다.

제일 왼쪽 도시에서 제일 오른쪽 도시로 가는데 최소 비용을 구하면 되는 문제이다.

제일 왼쪽 도시에서 출발하여 주유를 하며 오른쪽 도시로 이동하면 되는데, 이때 2가지 경우가 존재한다.

만약 해당 도시의 기름값이 제일 오른쪽 도착 도시를 제외한 나머지 도시의 기름값 중 최솟값이면 해당 도시에서 이동하려는 거리만큼 기름을 전부 넣으면 된다.

반면에 해당 도시의 기름값이 최솟값이 아니라면 현재 도시 이후의 도시들 중 현재 도시의 기름값보다 낮은 기름값을 갖는 도시까지만 이동하고 또 기름을 넣어야 최소 비용으로 이동할 수 있다.

이를 활용하면 최소 비용으로 제일 오른쪽 도시까지 이동할 수 있다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 도시의 개수를 입력받는다. n = int(sys.stdin.readline())
3. 인접한 두 도시를 연결하는 도로의 길이를 입력받는다. distance = list(map(int, sys.stdin.readline().split()))
4. 각 도시의 주유소 리터당 가격을 입력받는다. price = list(map(int, sys.stdin.readline().split()))
5. 제일 오른쪽 도시에서 기름을 넣을 경우는 없으므로 주유소 리터당 가격은 제외시킨다. price.pop()
6. 주유소 리터당 가격의 최솟값을 저장한다. MIN = min(price)
7. 최소 비용을 저장할 변수를 생성하고 초기화한다. result = 0
8. 현재 위치하고 있는 도시를 저장하는 변수를 생성하고 초기화한다. now = 0
9. 현재 도시가 마지막 도시 이전 도시이면 반복한다. while (now < n)
   1. 만약 현재 도시의 주유소 리터당 가격이 최솟값이면 if (price[now] == MIN)
      1. 현재 도시에서 기름을 모두 넣는다. result += sum(distance[now : ]) * price[now]
      2. 해당 기름으로 마지막 도시까지 가므로 최소 비용은 구해졌기에 종료한다. break
   2. 반면에 현재 도시의 주유소 리터당 가격이 최솟값이 아니면 else
      1. 다음 도시를 저장하는 변수를 생성하고 현재 도시 다음 위치를 저장한다. next = now + 1
      2. 현재 도시의 주유소 리터당 가격보다 낮은 가격의 도시가 나올 때까지 반복하며 다음 도시의 위치를 이동한다. while (price[now] < price[next]): next += 1
      3. 현재 도시의 주유소 리터당 가격보다 낮은 가격의 도시를 찾으면 해당 도시까지 이동할 기름을 넣는다. result += sum(distance[now : next]) * price[now]
      4. 이동 후 현재 도시의 위치를 새로 저장한다. now = next
10. 제일 오른쪽 도시까지 이동한 후, 최소 비용을 출력한다. print(result)

3. 소스코드 

import sys

n = int(sys.stdin.readline())
distance = list(map(int, sys.stdin.readline().split()))
price = list(map(int, sys.stdin.readline().split()))
price.pop()

MIN = min(price)
result = 0
now = 0
while (now < n):
    if (price[now] == MIN):
        result += sum(distance[now : ]) * price[now]
        break
    else:
        next = now + 1
        while (price[now] < price[next]):
            next += 1

        result += sum(distance[now : next]) * price[now]
        now = next

print(result)