heukhyeon   6년 전

dp[i]= 합계값 i에 대한 코인갯수 최소값
1)가장 가치가 작은 코인은 해당코인만으로 표현가능한경우에만 dp값 갱신
2)다음 코인부터

2-1)해당 코인만으로 표현가능할시 dp값 갱신
2-2)표현 불가능할시 몫=k, 나머지=l로 두면 value=k+dp[l];
2-2-1)이때 dp[l] = -1이면 표현불가능한걸로 간주

yys11631   6년 전

가치가 많은 동전을 가장 많이 사용한다고 동전을 최소로 사용하는건 아닙니다.

3 24

1

7

10

입력이 이럴 때 정답은 7원 2개 10원 1개를 사용해서 3이야 하지만 이 코드대로라면 1원 4개 10원 2개를 사용해서 6을 출력합니다.

n번째 동전까지 사용했을 때 k원을 만들 때 필요한 최소 동전 수를 dp[n][k]로 두고 풀어보세요.

heukhyeon   6년 전

무슨 말씀이신지 알것같아서 갱신해봣는데 91퍼에서 멈추네요...
일단 이차원배열로 다시 시도해봐야겠습니다

yys11631   6년 전

주어진 금액을 만들 수 없으면 -1 출력을 해야합니다(ex 2, 4, 6원 짜리론 1원을 만들 수 없다).

추가적으로 dp를 저렇게 사용한다면 굳이 동전의 크기를 소팅할 필요는 없습니다. 동전을 고르는데 순서는 중요하지 않기 때문이죠.

댓글을 작성하려면 로그인해야 합니다.