waylight3   8년 전

solve 함수는 money를 만들 수 있는 경우의 수 인데 이때 적어도 coin[c] 이상의 동전을 사용합니다.

중복을 제거하기 위해 무조건 작은 동전부터 쓰게 하려고 방금 쓴 동전이나 그보다 큰 동전만 쓰도록 하려구요.

(coin은 이미 main에서 정렬을 해 두었으니)

만약 불가능한 경우 (제일 작은 동전이 2인데 남은 돈이 1원이라던가) 당연히 ret이 for문을 안도니까 0으로 나올거구요.

이걸 DP로 만들려고 했는데 그 전에 시간초과가 뜨는지 돌려봤더니 그냥 틀렸다고 나옵니다 ㅠㅠ

제가 뭔가 잘못 생각하고 있는 건가요? ㅠㅠ

indioindio   8년 전

제가 인덱스에 약해서 해결법이 당장은 생각나지 않지만

입력받고 정렬하는 과정에서 문제가 있는 것 같네요

3 10

5 2 1

이라는 입력에 대해서는 3이라고 나오네요 (정렬을 하니까 3 10 1 2 5 와 solve의 구현과는 무관하게 같은 값 10이 나와야겠죠)

indioindio   8년 전

coin + N + 1 까지 정렬해야하나보네요

일단 소스상에 봤을 때 COIN 배열에 1부터 input값을 받으니

sort에서는 sort(coin+1,coin+n+1)을 해야 하지 않을까요?

waylight3   8년 전

말씀해주신대로 coin + N번 요소가 정렬되지 않았던 건 문제였던 것 같습니다.

이 점을 고치니 3 10 5 2 1 에 대해서도 10이 제대로 나오게 되었구요.

그런데 여전히 틀렸다고 하는데 논리 자체에 문제가 있는 걸까요?

indioindio   8년 전

3 10

10 2 5 같은경우에도 2가 나오네요

money >= coin[i]

i가 동전의 값에서 시작하는데 그걸 인덱스 삼아서 다시 동전배열을 참고해서 이런 에러들이 나는게 아닐까 싶네요


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