백준 #13305 - [S3] 주유소 : 그리디

(python3)

13305번: 주유소

 

 

그리디

처음엔 재귀로 접근했는데, min, 파싱한 배열 넘기기 등 불필요한 시간이 많이 드는 풀이였습니다.

 

단순하게 그리디로 접근하면 되는 문제입니다.

시작지점에서부터 진행하면서 지금까지 만난 가격중 가장 저렴한 주유소를 발견하면 그 가격을 저장하고, 더 저렴한 주유소가 나올때까지 거리를 갱신하면서 항상 가장 저렴한 가격을 유지하면 됩니다.

 

코드

def solution(input) : 
    N = int(input().strip())
    R = list(map(int,input().split()))
    C = list(map(int,input().split()))

    min_c = C[0] # 지금까지 나온 주유소 중에 가장 싼 가격
    fcost = 0 # 최종 코스트. 항상 최소값으로 유지
    m = 0 # min_c 가격으로 거리를 얼마나 더 가야 더 싼 가격이 나오는지
    for i in range(N-1) : # 마지막 주유소는 필요없음
        if min_c > C[i] : # 가장 싼 주유소 등장
            fcost += m*min_c
            min_c = C[i]
            m = R[i]
        else :
            m+=R[i]
    fcost += min_c*m
    print(fcost)

solution(input)

 

시간초과 재귀

def solution(input) : 
    N = int(input().strip())
    R = list(map(int,input().split()))
    C = list(map(int,input().split()))
    # 시간초과 
    def recur(road, cost) :
        fcost = 0
        if len(cost) <= 0 : return fcost
        midx = cost.index(min(cost)) # 가장 싼 가격의 주유소에서 끝까지 갈때까지 필요한 기름을 다 넣으면 됨
        c = cost[midx]
        min_c_dist = sum(road[midx:])
        fcost += c*min_c_dist
        fcost += recur(road[:midx],cost[:midx]) # 가장 싼 가격 주유소 전까지에서 재귀
        return fcost
    print(recur(R,C[:-1]))
    
solution(input)

 

my solved.ac :

solved.ac