코테/BOJ

백준 13305 [주유소] 파이썬

동 캄 2022. 2. 11. 10:54
반응형

https://www.acmicpc.net/problem/13305

 

13305번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net

n = int(input())
dis = list(map(int, input().split()))
city = list(map(int, input().split()))
city.pop()
i = 0
answer = 0
while i < len(dis):
    j = 0
    while (i+j+1) < len(dis) and city[i] <= city[i+j+1]:
        j += 1
    answer += sum(dis[i:i+j+1])*city[i]
    i = i+j+1
print(answer)

간단한 그리디 문제이다. 

cost가 작은 주유소가 나올때까지, cost* distance를 하여 더한다.

반응형