오늘의 문제는 i번 째 과일을 살 경우 i+1 종류의 다음 과일들을 공짜로 얻을 수 있을 때, 주어진 prices 가격표를 참고하여 어떤 과일들을 살 경우 가장 적은 가격으로 모든 과일을 얻을 수 있는지 return 하는 문제이다. 나는 dp로 접근하여 풀이하였으나, 정답에는 실패하여 다른 사람의 풀이를 참고하였다.
풀이는 다음과 같다.
dp를 큰 값으로 초기화 한다.
dp에 각 i에 필요한 최소 coin 수를 저장한다.
dp[0] = 0으로 세팅한다. (0을 만들기 위해 필요한 동전 수는 0)
prices list의 각 요소를 순회한다.
현재 dp 값과 현재 동전 값을 더한 합을 sdp로 할당한다.
dp를 업데이트 할 수 있는 위치들을 조회하며, dp를 다음과 같이 업데이트 한다. ⇒ 현재 dp 값 vs 계산된 sdp 값 중 더 작은 값을 찾아 dp 값을 갱신한다.
dp[N]을 조회하여 return 한다.
오늘은 dp 문제를 풀이하였다. dp 문제는 매번 접할 때마다 쉽지 않다는 생각을 하였는데, 오늘의 경우 더 어려웠던 것 같다. 이와 같은 유형은 연습만이 답이라고 하니, 꾸준하게 연습해서 실력을 늘리는 수 밖에 없겠단 생각이 들었다. 연습하자.