문제를 보자마자 벙 쪘다.. 어떻게 풀어야 할 지 감이 오지 않았다. 처음엔 모든 경우의 수를 다 방문해보면 되지 않나? 라고 생각했고 도시의 개수 N이 2 이상 100,000 이하라는 걸 보고 아닐 거라는 걸 알았다.
아이패드가 왔다. 공부하기에 최상의 조건이 갖춰졌다. 물론 장인은 도구를 탓하지 않는다. 하지만 장인에게도 보다 더 좋은 도구가 있다면 이전에 비해 훨씬 뛰어난 결과를 내보일 수 있을 것이 분명하다. 아이패드가 있으면 더 좋을텐데와 같은 댈 수 있는 핑계도 없다. 쫄지 말고 머리부터 박자. 남 눈치 보지말고 나만의 페이스대로 간다. 할 수 있다. 끝까지 가면 내가 무조건 이긴다. 항상 그래왔으니까. 일단 뭐든 해보자. 뭐든 할 수 있는 나이가 아닌가. 절대 늦지 않았다.
도대체 어떻게 풀어야 할 지 모르겠더라. 문제를 보고 어떻게 풀 지 생각하는데 시간이 꽤 걸렸고 그래서 문제 분류를 봤다.
그리디 알고리즘
아 드디어 그리디 알고리즘 이구나... 학부과정에서 한번 배우긴 했지만 개념을 정확하게는 모르고 있었기에 구글링과 유튜브에 나와있는 강의들을 통해 개념부터 익혔다. 이 내용은 따로 포스팅을 해서 기록해두려고 한다. 두고두고 봐야지 이래놓고 안봄
핵심은 바로
매번 그 순간에 가장 최적인 답을 고른다 => 근시안적인 선택
관찰을 통해 탐색 범위를 줄인다
이 문제에 적용해보면
도시의 기름값(price) 배열을 탐색하면서 현재의 최저값(minimum price)보다 더 작은 값이 나오면 현재의 최저값을 해당 값으로 갱신한다.
제일 처음 기름값을 minPrice 라 두고 for문을 순회한다. 그 끝은 항상 answer(그 때까지 갈 때 얼마인지 => 현재의 최저값 * 거리)의 계산이다.
N = int(input())
distanceList = []
priceList = []
answer = 0
distanceList = list(map(int, input().split()))
priceList = list(map(int, input().split()))
minPrice = priceList[0]
for i in range(N-1):
if minPrice > priceList[i]:
minPrice = priceList[i]
answer += minPrice * distanceList[i]
print(answer)
그에게 주어지는 합격 목걸이
맞췄습니다!!!
