[백준-파이썬] 13305-주유소

문제바로가기

n = int(input())
dis = list(map(int, input().split())) # 사용기름 2 3 5
city = list(map(int, input().split())) # 기름가격 5 4 9 2

prefix = [0]*(n)

if n<=2:
    print(city[0] * dis[0])
else:
    for c in range(1, n):
        prefix[c] = prefix[c-1] + min(city[:c]) * dis[c-1]
        
print(prefix[-1])

위 코드는 41점짜리다. 서브테스크 문제라서 n의 크기에 제약이 있으면 점수를 절반만 준다. 위 코드가 시간 복잡도가 큰 이유는 min연산이다. min만보더라도 $O(n)$인데 이걸 for문만큼 반복하기 때문에 총 $O(n^2)$만큼의 복잡도를 갖게 된다. min을 아주 조금만 바꿔주면 100점짜리로 바꿀 수 있다.

n = int(input())
dis = list(map(int, input().split())) # 사용기름 2 3 5
city = list(map(int, input().split())) # 기름가격 5 4 9 2

prefix = [0]*(n)
min_l = city[0]

if n<=2:
    print(city[0] * dis[0])
else:
    for c in range(1, n):
        min_l = min(min_l, city[c-1])
        prefix[c] = prefix[c-1] + min_l * dis[c-1]
        
print(prefix[-1])

바로 이렇게 어떤 변수에 이미 최소 기름값을 저장해두고 딱 현재 도시와 비교하면 된다. 두 수를 비교하는 것은 $O(1)$이기 때문에 도시의 크기 n과 연관이 없다.