백준 13305 - 파이썬

문제를 정리해보면 각 도시마다 리터당 기름의 가격이 최종 목적지까지의 거리가 정해져 있다. 최종 도시까지 이동할때 가장 적은 기름의 가격을 지불하여 이동하는것이 문제이다.

 

처음에 생각해낸 문제 풀이는 1번 도시와 2번 도시와의 기름 가격을 비교하고 출발하는 도시에서의 기름 가격이 더 비쌀 경우 최소한의 거리량만 기름을 주유하고, 그 다음 도시보다 지금 도시가 더 쌀 경우 두개의 도시를 이동할 거리의 기름량을 충전하고 계산하도록 하는 것이다. 

n = int(input())

distance = list(map(int,input().split()))
priceOfOil = list(map(int, input().split()))

price = 0
i = 0

while i < n-1:
  if priceOfOil[i] < priceOfOil[i+1]:
    price+= (distance[i] + distance[i+1]) * priceOfOil[i]
    i+=2
  else:
    price += distance[i] * priceOfOil[i]
    i+=1

print(price)

for문을 돌면서 필요한 인덱스를 찾아 그 인덱스만큼 처음부터 더하는 식으로 풀어봤다. 하지만 이렇게 제출했을 경우에는 서브테스크 1번 밖에 통과가 안 되었다. 고민을 거듭했지만 더 나은 해결 방법을 찾지 못하고 다른 사람의 풀이를 참고해보기로 하였다.

n = int(input())
roads = list(map(int, input().split()))
costs = list(map(int, input().split()))

res = roads[0] * costs[0]
m = costs[0]
dist = 0

for i in range(1, n-1):
  if costs[i] < m:
    res += m*dist
    dist = roads[i]
    m = costs[i]
  else:
    dist += roads[i]

  if i == n-2:
    res += m * dist

print(res)

for문을 돌면서 주유 가격이 지금보다 쌀 경우에는 가장 작았던 주유 가격과 지금까지 왔던 거리를 곱해준 뒤 결과에 더해준다.

그 다음 주유 가격이 제일 작은 가격으로 바꿔주다.

마지막 도로에서는 가격을 전부 계산해준다.

 

이렇게 풀이를 하니 서브 태스크를 모두 통과할 수 있었다.

 

또 다른 풀이가 있나 구글링을 하며 찾아보았는데 이게 더 간결한거 같다.

import sys
input = sys.stdin.readline

n = int(input())

roads = list(map(int, input().split())) # 2 3 1
costs = list(map(int, input().split())) # 5 2 4 1

min_price = roads[0] * costs[0]
min_cost = costs[0]

for i in range(1, n-1):
  if min_cost > costs[i]:
    min_cost = costs[i]

  min_price += min_cost *roads[i]

이 풀이는 최소가격을 찾기 위해 반복문을 돌지 않고, 최소가격을 찾으면 바로 더해주는 식으로 풀이한 것이다. 문제에서 원하는 것은 최소가격을 구하기 위한 각 도시들의 인덱스가 아닌, 최소가격을 원하는 것이기 때문에 이렇게 풀이하는 것이 더 효율적인거 같다.

 

이번 문제를 풀면서 느낀 점은 문제가 원하는 답에 따라서 코드의 구성과 효율성이 달라진다는 점이다. 같은 답이어도 더 효율적이게 짠 코드가 더 나은 코드이니 문제가 원하는 답에 대한 가장 최적의 코드를 구현하려고 노력해야 되겠다. 물론 당연한 거긴 하지만...!