[BOJ] 13305번 | 주유소 (Python3)

🔗문제 보러가기

13305번: 주유소

 

 

문제 설명

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 

 

 

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

 

---

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다. 

 

---

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.

 

---

서브태스크

 

---

예제 입출력

 

---

풀이 전략

도시 개수와 거리, 기름값이 굉장히 큰 수가 나올 수도 있어서 오버플로우(overflow)를 걱정했는데, Python3의 정수형 범위에 제한이 없더군요. 그래서 별 걱정없이 그대로 사용했습니다. 저는 다음과 같이 풀었습니다.

• 입력받을 때, 모든 거리의 총합과 가장 값 싼 기름 값을 별도로 저장해둔다.
• 현재 내가 머무르는 도시의 기름값  ≤  다음 도시의 기름값
  • 다음 도시까지 거리만큼의 기름을 구매한다.
  • 이동 거리에 다음 도시까지의 거리만큼을 추가한다.
  • 그 다음 도시의 기름 값을 살펴본다.
  • 그 다음 도시 역시 비싸다면 위 과정 반복
• 현재 내가 머무르는 도시의 기름값  >  다음 도시의 기름값
  • 다음 도시까지 거리만큼의 기름을 구매한다.
  • 이동 거리에 다음 도시까지의 거리만큼을 추가한다.
  • 모든 거리의 총합에서 이동한만큼의 거리를 뺀다.
  • 이동 거리를 0으로 다시 초기화한다.
• 마지막 도시의 전 도시에 도착했다면 남은 거리만큼 기름을 사면 끝
• 만약 중간에 기름이 가장 싼 도시에 도착했다면, 남은 총 거리만큼 기름을 사고 끝

시나리오

• 예를 들어, 다음과 같이 도시 5개가 존재한다고 가정합시다.
• 입력 받을 때, 총 거리의 합과 제일 싼 기름값을 별도로 저장해둡니다.

• 두 번째 도시를 살펴보니 현재 도시보다 기름 값이 비쌉니다. 두 번째 도시까지의 기름을 구매하고, 이동 거리를 저장합니다.

• 그 다음 도시도 살펴보니 역시 비쌉니다. 두 번째 도시에서 세 번째 도시 사이의 거리만큼 기름 값을 구매하고 거리도 저장해줍니다.

• 네 번째 도시를 살펴보니, 현재 도시보다 기름 값이 쌉니다. 하지만 네 번째 도시로 가기 위해서는 세 번째 도시와 네 번째 도시 사이의 거리만큼 기름도 필요하므로 구매해줍니다.
• 첫 번째 도시에서 네 번째 도시까지 가는데 걸리는 거리를 총 거리에서 빼줍니다. ( 12 - 7 = 5km)
• 이동 거리를 0으로 초기화해줍니다.

• 네 번째 도시에 와보니 시나리오 종료 조건 두 개를 모두 만족합니다.
  • 마지막 전 도시까지 온 상황일 경우
  • 제일 값 싼 기름 값을 보유하고 있는 도시일 경우
• 둘 중 하나만 만족해도 되고, 둘 중 어느 걸 하더라도 똑같은 결과이므로 진행해줍니다.

 

이로써 최소 비용 50원만큼만 기름을 구매하면 이동을 완료할 수 있습니다.

만약 중간에 제일 싼 기름 값을 가지는 도시를 만나게 되면 어떻게 될까요?

 

중간에 제일 값 싼 기름값의 도시를 만날 경우

• 위 시나리오에서 두 번째 도시와 네 번째 도시만 바꿔보았습니다.

• 현재 도시에서 다음 도시를 보니, 현재 도시보다 기름값이 쌉니다. 다음 도시까지 거리만큼의 기름만 구매하고, 총 거리에서 해당 거리를 빼줍시다.

• 두 번째 도시에 와 보니, 제일 기름 값이 싼 도시입니다. 이 경우 남은 총 거리만큼 여기서 기름을 구매하면 되므로, 뒤에 남은 도시들은 살펴볼 필요가 없습니다.

 

이로써, 기름 값을 최소로 40원만 들이면 모든 도시를 이동할 수 있습니다.

 

---

소스 코드 및 결과

# Python3는 정수 범위가 무제한

N = int(input())           # 도시의 개수 (2 <= N <= 100000)
distances = list(map(int, input().split()))
oilCosts = list(map(int, input().split()))
totalDistance = sum(distances)
minOilCost = min(oilCosts)

#---------------------------------------------------------------------

def Solution(distances, totalDistance, oilCosts, minOilCost):
    i = 0
    totalOilCost = 0
    
    while i < N - 1:                           # 마지막 도시 전까지만 체크하면 됨
        currentOilCost = oilCosts[i]
        isNextLastCity = (i == N - 2)
        moveDistance = 0
    
        if isNextLastCity:                     # 마지막 전 도시까지 왔다면 그 도시에서 남은 거리만큼 기름 사면 끝
            totalOilCost += currentOilCost * totalDistance
            return totalOilCost
    
        while oilCosts[i+1] >= currentOilCost: # 다음 도시 기름값이 현재 내가 머무르는 도시 기름값보다 비쌀 경우
            betweenDistance = distances[i]     # 현재 도시 기름값보다 값 싼 도시가 나올 때까지 이동할만큼의 기름을 현재 도시에서 구매
            moveDistance += betweenDistance
            totalOilCost += currentOilCost * betweenDistance
            i += 1
        
            if i == N - 2:
                break
        
        # 기름값이 싼 도시와 그 이전 도시 사이의 거리만큼 기름 구매가 while문 조건에 의해 생략됐으므로 진행
        betweenDistance = distances[i]
        moveDistance += betweenDistance
        totalOilCost += currentOilCost * betweenDistance
        totalDistance -= moveDistance
        i += 1
    
        if oilCosts[i] == minOilCost:   # 제일 값 싼 주유소를 찾았다면 남은 거리만큼 사고 끝
            totalOilCost += minOilCost * totalDistance
            return totalOilCost
    


result = Solution(distances, totalDistance, oilCosts, minOilCost)
print(result)