heogj123   10달 전

2293번 동전 1이랑 비슷하게 풀었는데요

우선 인풋들 퀵소트로 정렬하고 작은것부터 인풋을 받도록했어요

그리고 가지고있는 동전으로 나누어떨어지는 금액인경우 1로 초기화하여 다음 DP에 적용하도록하였고요..

어느 테스트케이스에서 걸리는지를 모르겠네요 ㅠㅠㅠ


---------------------------------------------------------------------------------------------------------------------------------------

다시 수정하여 코드를 짜봤습니다.

큰틀은 그대로이고 왠만한 인풋 다 한번씩 넣어봤다고 생각하는데 어디서 틀린건지..

고수님들 지나가는길에 한번씩만이라도 봐주고 가세요 ㅠㅠㅠ

whgusfud   10달 전

3 15

13

12

11

input으로 넣으면 1이 나오네요..... -1이 나와야 할텐데????????

whgusfud   10달 전

이 문제에대해 힌트를 좀 드리자면,
일반적인 문제들과 다르게, 이 문제에서는 큰거부터 꽉꽉 채워넣었을 때가 답이 아닐 수 있습니다.
예제로 나온 3 , 15, 1 , 5, 12를 보아도 알 수 있는데, 
12 1 1 1 = 15 (4) > 5 5 5 = 15 (3)

저는 다음과 같은 방식으로 했습니다.

1, dfs 방식으로 완전탐색. 

2. dp로 시간단축

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