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]를 고르는 경우를 구하고 있는데

혹시 위와 같은 알고리즘에서 놓치는 경우의 수가 무엇이 있는지 궁금합니다.

evan3233   1년 전

출처: 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

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