프로그래밍/Python
[Python] 백준 13305 주유소
모영이
2021. 2. 19. 23:36
13305번: 주유소
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1
www.acmicpc.net
그리디 알고리즘 : 처음에는 주유소 배열에서 최솟값 인덱스를 찾고 도로를 슬라이싱 해서 도로의 합 X 주유소 최솟값을 해주고, 주유소 최솟값 인덱스 뒤에 값들을 슬라이싱으로 다 제거 했다. 이렇게 해서 답은 나왔는데 시간 초과와 말도 안되는 비효율이 났다. 순서대로 for문을 돌아도 충분히 된다..!
1) for문을 돌며 min_value에 주유소 최솟값을 업데이트 한다.
단 첫번째의 경우 무조건 주유소를 들러야 한다.
2) (min_value * 도로의 값)을 계속 더해주면 된다.
전체 코드
import sys
input = sys.stdin.readline
N = int(input())
doro = list(map(int, input().split()))
juyouso = list(map(int, input().split()))
min_value = sys.maxsize
sum = 0
for i in range(N-1):
if i == 0:
sum += juyouso[0] * doro[0]
min_value = min(min_value, juyouso[0])
else:
min_value = min(min_value, juyouso[i])
sum += min_value * doro[i]
print(sum)