[BOJ][Python]13305 풀이

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

13305번: 주유소

n = int(input())
l = list(map(int, input().split()))
p = list(map(int, input().split()))
min_p = p[0]
ans = 0
for i in range(1, len(p)):
    ans += l[i-1] * min_p
    if p[i] < min_p:
        min_p = p[i]
print(ans)

정말 제가 그리디를 잘 안푼다는게 여실히 드러나는 문제가 아니었나 싶습니다. 아직 그리디 알고리즘을 이해하지 못하는 것 같기도 하구요. 그냥 말로는 그 순간의 최적의 해를 구한다 하고 알고있지만 그걸 토대로 코드를 짤 줄 모르는 것 같습니다.

 

문제가 원하는 것은 굉장히 간단합니다. 최소한의 가격이 나오기 위해서는 현재의 위치보다 싼 가격이 나올 때까지 필요한 만큼만 기름을 넣으면 된다는 것이죠. 그래서 막 어렵게 현재의 위치를 저장해뒀다가 인덱스로 불러왔다가 혼자서 생쇼를 했는데, 다른 분들 코드를 보니까 그냥 그 때 그 때 더하면 되더라구요. 어떻게든 어렵게 생각하고 한 번에 하려고 하는 저의 성격면에서의 단점도 알게해주는 문제가 아니었나 싶습니다.

 

자기 반성이 길었습니다. 위의 코드를 토대로 문제 설명을 이어나가자면,

시작할 때 최소금액을 맨 처음 가격으로 선정합니다. 그리고 다음 주유소까지 이동을 하죠. 당연히 이동하는데에 든 비용이 있으니 정답에 더해줍니다. 그리고 최소금액보다 싼 가격이라면, 최소 금액을 갱신합니다. 첫번째 노드는 현재 위치이므로 반복문은 1번 인덱스부터 진행합니다.

 

설명도 정말 별게 없습니다. 어떻게 하면 좀 더 간단하게 생각할 수 있을지를 물어 본 문제라는 생각이드네요. 많은 연습이 필요할 것 같습니다.