출처: https://testcase.ac/problems/2...
반례 발견
총 테스트케이스 실행 개수: 100정답 개수 (정답 코드와 출력이 같음): 99,반례 개수 (정답 코드와 출력이 다름): 1
입력:
74 9184 53458 65436 35092 91613 35746 90628 21466 32931 36591 34901 15768 94776 59549 55561 62557 10383 11056 37676 9451 1343 42978 43692 81455 1730 77870 62571 313 48375 25691 54576 28377 1790 28071 15125 23895 47877 45483 97261 93412(...truncated, total 441 characters, 75 lines)
오답 출력:
15
정답 출력:
8

leomessi 1년 전
top-down 방식입니다.
32번 행에서 다음 재귀에서 pick할 동전의 종류를 현재 동전 이후의 동전들만 고려하도록 하였을 때 23%에서 오답 처리 되었습니다.
동전을 고르는 순서를 고려하지 않고 골라 중복해서 세는 경우를 제외하려고 하였습니다.
예시
(1원과 2원짜리 동전으로 5원을 만든다고 할 때, (1, 2, 2)순서대로 고르나 (2,1,2) 순서대로 고르나 (2,2,1) 순서대로 고르나 똑같이 3개의 동전으로 5원을 구성하게 된다.)
즉, coins가 동전들의 집합이라고 할 때, 0 <= i < j <= N인 두 정수 i, j에 대해서
이미 coins[i]를 몇 개 고를지 결정하고 그에 맞춰서 coins[j]를 고르는 경우를 구하고 있는데
혹시 위와 같은 알고리즘에서 놓치는 경우의 수가 무엇이 있는지 궁금합니다.