인프런 커뮤니티 질문&답변

dp 문제 중 효율적인 화폐 구성이라는 문제가 있는데요.

k개의 화폐로 n원을 만들 때 가작 작은 화폐 개수를 구하는 문제입니다.

예를 들어, k = 2, 3, 5로 구성되어 있고, n = 7, 정답이 a(n)이라면,

7 = 2 + 5이므로, a(7) = 2 개가 되는 문제입니다.

 

여기서 점화식은 a(n) = min( a(n), a(n-k) + 1 ),

a(n-k) + 1: 화폐 k원을 반드시 사용하는 경우를 의미

위의 예시에 점화식을 적용해본다면, 시작 전 a(n)을 모두 INF 값으로 초기화,

a(7) = min( a(7), a(7-2)+1, a(7-3)+1, a(7-5)+1 ) = min( a(7), a(5)+1, a(4)+1, a(2)+1 )

 

여기까지는 이해가 됐는데요,

설명이나 코드를 찾아보면 반복문의 위치가 제가 생각한거랑 반대로 돼있더라구요ㅠㅠ

저는 n에 대한 루프 안에 k의 루프가 와야 위의 점화식과 같은 방식이 된다고 생각했지만,

설명에서는 k = 2일 때 n=0~7까지 a(n)을 쫘르륵 구하고, 그다음 k = 3일 떄 쫘르륵, 마지막 k=7일 때 쭉 구해서 최종답을 구합니다.

 

왜 반복문의 위치가 이렇게 바뀌는 건가요??

아시는 분 답변 주시면 정말 감사하겠습니다ㅠㅠ