ghks285   1년 전

예제는 정확하게 나오는데 제출만하면 계속 틀리다고 나오는데 어디 부분이 틀렸는지 알 수 있을까요...

wizardrabbit   1년 전

안녕하세요? 반례 드립니다:

입력:
4 10
1 1 1 9

정답:
3

출력:
11

▲ 위 반례에서 합쳐질 수 있는 경우는 3(1+1+1), 11(9+1+1) 이며, 이 중 11(9+1+1)은 M값인 10을 넘으므로 사용할 수 없습니다. 따라서 정답은 3이어야 합니다.

입력:
4 100010
1 1 1

정답:
3

출력:
0

▲ 합쳐질 수 있는 경우는 3(1+1+1) 뿐이므로 정답은 3이어야 합니다.

틀린 원인을 정리해 보면:
1) 최적의 값을 구하는 기준을 절댓값으로 구하신 점 (첫 번째 반례)
2) 초기 min 값이 너무 작게 설정된 점 (두 번째 반례)
라 할 수 있습니다.

1)의 경우 abs, 즉 절댓값을 기준으로 최적의 값을 찾고 있기 때문에 첫 번째 반례에서 나오게 되는 값인 3과 11 중 10과의 절댓값 차이가 더 적은 11을 출력하고 있습니다만, 문제의 조건에 의하면 플레이어가 고른 카드의 합은 M을 넘지 않아야 하므로, 절댓값을 사용해서는 안 됨을 알 수 있습니다.

2)의 경우 min 값, 즉 M 값과의 차이가 가장 작은 값이 저장되는 값의 초기값이 100,000 인데, 두 번째 반례에 의하면 1, 1, 1을 합쳐 3을 만들었을 때의 M 값과의 차이는 300,000 - 3 = 299,997이 됩니다. 설정하신 min 값인 100,000보다 더 비효율적인 경우기 때문에 프로그램이 이를 건너뛰고 있습니다. 따라서 min 값이 가장 최악의 경우를 초기값으로 둘 수 있도록 min 값을 조절하셔야 함을 알 수 있습니다.

위의 틀린 원인 두 가지에 유의하시고, 올바르게 코드를 수정하시면 되겠습니다!

ghks285   1년 전

감사합니다!

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