안녕하세요? 반례 드립니다:
입력: 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년 전
예제는 정확하게 나오는데 제출만하면 계속 틀리다고 나오는데 어디 부분이 틀렸는지 알 수 있을까요...