제가 인덱스에 약해서 해결법이 당장은 생각나지 않지만
입력받고 정렬하는 과정에서 문제가 있는 것 같네요
3 10
5 2 1
이라는 입력에 대해서는 3이라고 나오네요 (정렬을 하니까 3 10 1 2 5 와 solve의 구현과는 무관하게 같은 값 10이 나와야겠죠)
2293번 - 동전 1
제가 인덱스에 약해서 해결법이 당장은 생각나지 않지만
입력받고 정렬하는 과정에서 문제가 있는 것 같네요
3 10
5 2 1
이라는 입력에 대해서는 3이라고 나오네요 (정렬을 하니까 3 10 1 2 5 와 solve의 구현과는 무관하게 같은 값 10이 나와야겠죠)
coin + N + 1 까지 정렬해야하나보네요
일단 소스상에 봤을 때 COIN 배열에 1부터 input값을 받으니
sort에서는 sort(coin+1,coin+n+1)을 해야 하지 않을까요?
3 10
10 2 5 같은경우에도 2가 나오네요
money >= coin[i]
i가 동전의 값에서 시작하는데 그걸 인덱스 삼아서 다시 동전배열을 참고해서 이런 에러들이 나는게 아닐까 싶네요
댓글을 작성하려면 로그인해야 합니다.
waylight3 8년 전
solve 함수는 money를 만들 수 있는 경우의 수 인데 이때 적어도 coin[c] 이상의 동전을 사용합니다.
중복을 제거하기 위해 무조건 작은 동전부터 쓰게 하려고 방금 쓴 동전이나 그보다 큰 동전만 쓰도록 하려구요.
(coin은 이미 main에서 정렬을 해 두었으니)
만약 불가능한 경우 (제일 작은 동전이 2인데 남은 돈이 1원이라던가) 당연히 ret이 for문을 안도니까 0으로 나올거구요.
이걸 DP로 만들려고 했는데 그 전에 시간초과가 뜨는지 돌려봤더니 그냥 틀렸다고 나옵니다 ㅠㅠ
제가 뭔가 잘못 생각하고 있는 건가요? ㅠㅠ