[백준/알고리즘/python/java] 13305번 - 주유소

이미지를 누르면 문제링크를 보실 수 있습니다.

이미지를 누르면 문제링크를 보실 수 있습니다.

[13305번 - 주유소]

전형적인 그리디 알고리즘 문제이다.

처음에는 계속 시간초과 문제를 해결하지 못했었다.

처음에 풀었던 코드는 이러했다.

 

n = int(input())
roads = list(map(int, input().split()))
prices = list(map(int, input().split()))
total = prices[0] * roads[0]  # 출발 도시의 기름가격 x 출발 도시와 두번째 도시 사이의 도로길이 
previous_price = prices[0]    # previous_price 에 우선 출발 도시의 가격 저장
# k 라는 변수를 1로 잡았다(두번째 도시와 세번째 도시 사이의 도로 길이 인덱스는 1 이므로)
k = 1  # 도시 간격(도로 길이)를 나타내는 인덱스

for i in prices[1:]:              # 두번째 도시부터 기름가격 리스트 for문을 도는데, 
    if (i <= previous_price):     # 그 가격이 이전도시의 기름 가격보다 낮다면
        previous_price = i        # 우선 previous_price 를 해당 도시의 기름가격으로 변화시켜주고
        for j in roads[k:]:       # 도로 길이 리스트 for문을 돈다.
            total += previous_price * j    # 해당 도시 기름가격 x 해당 도시와 다음 도시 사이의 길이
            k += 1      # k 는 1 증가 시켜준다.
            break
    else:                        # 그 가격이 이전도시의 기름 가격보다 높다면
        for j in roads[k:]:      # previou_price를 새로 업데이트 할 필요 없이 (이전 가격이 더 싸니까)
            total += previous_price * j     # 바로 previous_price x 해당 도시와 다음 도시 사이의 길이
            k += 1      # k 는 역시 1 증가 시켜준다.
            break    

print(total)  # 총 가격을 출력

답은 제대로 나왔지만, 지금 반복문의 수가 너무 많았다.

반복문의 수를 줄여야 하는데, 관건은 각 도시들을 지나쳐오면서 이전 도시에서의 기름 가격보다 낮은 가격이면

그 가격을 바꿔가면서 해당 가격에 도로의 길이를 곱해줘야 했다.

 

설마 for문이 중복되어서 그런가 해서 아래 코드처럼 줄여봤지만, 시간복잡도에는 변화가 없었다.

n = int(input())
roades = list(map(int, input().split()))
prices = list(map(int, input().split()))
total = prices[0] * roades[0]
previous_price = prices[0]
k = 1
for i in prices[1:]:
    for j in roades[k:]:
        if (i <= previous_price):
            previous_price = i
            total += previous_price * j
            k += 1
            break
        else:
            total += previous_price * j
            k += 1
            break

print(total)

그렇다면, 도시의 기름 가격 리스트 중에 최소 가격을 애초에 미리 찾고

그 최소가격이 발견된 시점부터는 쭉 최소가격으로 도로의 길이를 곱하면 되니까 

반복문을 덜 돌지 않을까 싶어서 아래코드로도 바꿔봤지만, 역시 시간 초과가 발생하였다.

 

n = int(input())
roades = list(map(int, input().split()))
prices = list(map(int, input().split()))
min_Price = min(prices[:-2])  # 애초에 시작할 때 기름가격 리스트에서 최소값을 min_Price에 저장

total = prices[0] * roades[0]

previous_price = prices[0]
k = 1
for i in prices[1:prices.index(min_Price)+1]:
    for j in roades[k:prices.index(min_Price)]:
        if (i <= previous_price):
            previous_price = i
            total += previous_price * j
            k += 1
            break
        else:
            total += previous_price * j
            k += 1
            break
if prices.index(min_Price) != 0:   
    for m in roades[prices.index(min_Price):]:
        total += min_Price * m
else:      # 출발 도시 기름가격이 min_Price 일 수도 있으니까, 그렇게 되면 다음 도시부터 계산을 해야한다.
    for m in roades[prices.index(min_Price)+1:]:
        total += min_Price * m
print(total)

관건은 결국 반복문을 아예 줄여야 했다.

단순히 생각해보면 도시를 거쳐오면서 계속해서 최소 기름가격을 갱신하면 간단한 문제인 것이다.

결국에는 for문 한개로도 해결이 되는 문제였다.

 

(마지막 최종 python 코드)

n = int(input())
roads = list(map(int, input().split()))
prices = list(map(int, input().split()))
min_Price = prices[0]          # 우선 min_Price 를 출발 도시 기름가격으로 초기화

total = 0
for i in range(n-1):     # 도시를 돌면서 마지막 도시는 사실상 무미(도시 간격까지 이므로 n-1)
    if i == 0:  		 # 출발 도시일 때는 우선 출발을 해야하니까  
        total += prices[0] * roads[0] 			# total 에 (해당 도시 기름가격 x 도로 길이) 필수
        min_Price = min(min_Price, prices[i])   # 현재는 min_Price가 당연히 출발도시 기름가격
    else:			     # 출발 도시를 제외한 도시에서는 
        min_Price = min(min_Price, prices[i])   # 해당 도시 기름가격이 현재 최소가격보다 높은지 낮은지 체크하는 것이 먼저여야 한다.  
        total += min_Price * roads[i]  			# (최소 가격 x 도로 길이)
print(total)

결국 각 도시의 기름 가격 중에 최소값을 찾는 것이 포인트였는데,

for문을 하나만 써도 최소 기름가격을 계속 갱신하면서 도로를 지나쳐올 수 있었다.

 

전형적인 그리디 알고리즘은 결국 반복문의 수를 줄이는 것이 관건인 것 같다. 

또한, 코드의 플로우를 잘 고려하여 

코드의 순서만 바꿔줘도 아예 다른 기능을 하도록 만들 수 있었다.

생각의 폭을 넓혀야 한다.