S3 13305. 주유소

문제 보기 :  13305번: 주유소

---

문제

• 정답률 : 39%

 

---

작성 코드 & 풀이

nodes = int(input())

#노드별 거리
distance = list(map(int,input().split()))
dist = sum(distance)

# 1리터당 가격
price = list(map(int,input().split()))

l = [0]*nodes

for i in range(nodes):
    k = 0 ; passdist = 0
    for j in range(i):
        passdist += distance[j]
        k += price[j]*distance[j]
    k += price[i]*(dist-passdist)
    l[i] = k

print(min(l))

처음 작성한 코드가 틀린 이유는 효율성과 논리적인 문제에 있었다.

문제는 주어진 거리와 주유소 가격에 따라 최소 비용으로 이동할 방법을 계산하는 것이지만, 현재 코드는 불필요한 연산을 반복적으로 수행하고 있어 시간 복잡도가 매우 높아지고, 논리적으로도 최소 비용 계산이 올바르지 않았다.

그래서 아래와 같이 수정했다.

nodes = int(input()) # 도시 수
distance = list(map(int,input().split()))  # 도시 간 거리
price = list(map(int,input().split())) # 1리터당 가격

min_price = price[0] #현재 위치에서 가장 저렴한 가격 선택
total = 0 # 최소 비용

for i in range(nodes-1):
    min_price = min(min_price, price[i]) # 가장 저렴한 가격 갱신
    total += min_price*distance[i] # 현재 거리만큼 주유 비용 계산

print(total)

1. 도시 수와 각 도시 간 거리, 주유소 가격을 입력받는다.

2. 첫 번째 주유소 가격을 가장 저렴한 가격으로 초기화한다.

3. 현재 도시까지의 가장 저렴한 가격으로 필요한 거리만큼 주유 비용을 계산한다.

4. 다음 도시로 이동할 때, 현재 주유소와 이전까지의 가장 저렴한 가격을 비교하여 갱신한다.

5. 모든 도시를 순회하며 최소 주유 비용을 누적 계산한다.

6. 마지막 도시에 도착한 후 최소 비용을 출력한다.