[알고리즘] 백준13305 주유소 - 파이썬

단계별 풀기 '그리디 파트'의 마지막 문제를 풀어보았습니다. 이번 문제는 특이하게 서브 태스크가 있었는데 제약조건에 따라 부분점수를 주는 것 같습니다. 만점을 받지는 못했지만 예제 입력에 따른 답은 잘 나오는 편이었습니다.

 

 

[나의 풀이]

from sys import stdin

n = int(input())

km_list = stdin.readline().split() # 거리입력
price_list = stdin.readline().split() # 주요소 가격

result = 0
for i in range(len(km_list)):
    a = []
    for j in range(i+1):
        k_p = int(km_list[i]) * int(price_list[j])
        a.append(int(k_p))

    result += min(a)

print(result)

- 제 코드의 핵심? 이라고 생각한 부분은 for문에서 두 번째 도시부터는 앞으로 가야 할 거리(km)와 처음 주유소의 가격의 곱과 현재 위치한 두 번째의 주유소의 가격의 곱을 비교해서 최솟값을 결괏값에 누적하여 더해주는 것이었습니다. 

 

- 예를 들면 15(=3km x 5) 와 6(=3km x 2)을 비교해서 최솟값을 결괏값을 누적하는 것입니다.  

 

[다른 분의 풀이]

N = int(input())
roads = list(map(int, input().split()))
cities = list(map(int, input().split()))

minVal = cities[0]
sum = 0
for i in range(N - 1):
    if minVal > cities[i]:
        minVal = cities[i]
    sum += (minVal * roads[i])

print(sum)

- 다른분의 코드를 보니 제 코드에서는 불필요하게 리스트와 for문이 들어갔었습니다. 첫 주유소가격을 최솟값 변수에 넣어둔 후 도시를 이동할 때마다 주유소 값을 비교하는 것이 더 효율적이었습니다.