테스트 데이터의 경우 전체 개수는 크게 중요하지 않습니다. 자기가 통과시키려고 한 솔루션들은 통과시키고, 막으려고 한 솔루션들은 막을 수만 있으면 됩니다.
구간 합 구하기 문제의 경우 전체적으로 답을 잘 출력하는지 보려면 N, M, K 최대로 랜덤하게 몇 개만 해보더라도 괜찮습니다. 출력의 양 자체가 많기 때문에, 틀린 알고리즘이었다면 매우 높은 확률로 1개의 랜덤 테스트에서도 오답을 출력할 가능성이 높기 때문입니다.
하지만 저 문제에서 또 막아야 하는 것이 있습니다. 우선 long long을 쓰지 않고 int를 쓴 솔루션이 통과되지 못해야 합니다. 그런 솔루션을 방지하기 위한 테스트를 또 한두 개 만들면 됩니다.
그리고 또한 naive하게 구간의 합을 구하는 솔루션 역시 막아야 하는데 이건 어떻게 하면 좋을까요? 최대 N 크기에서 처음부터 끝까지의 합을 계속 출력하게 하면 최악의 케이스가 될 것입니다.
그런데 이런 걸 또 뚫고 싶은 사람들이 메모이제이션 같은 걸 할 수도 있습니다. [a, b]에 대한 합을 구한 적이 있고 그 사이에서 값을 변경한 적이 없다면 이전에 구해둔 결과를 그대로 출력해버리는 식으로요. 그럼 이걸 어떻게 막으면 좋을까요? 값 변경과 합 출력을 번갈아가면서 하거나, 아니면 [a, b], [a, b - 1], [a, b - 2], ... 과 같이 범위는 넓게 유지하되 매번 조금씩 다른 구간을 넣어줄 수도 있습니다.
이런 식으로 "통과되어서는 안 되는 코드"가 어떤 것들이 있을지 생각해보고, 그들을 저격하는 데이터들을 만들어내는 걸 중점적으로 생각하시면 됩니다.
degurii 5년 전
다름이 아니라 이번에 문제를 출제하게 되었는데요...
이쪽으로는 아예 처음이라 힘든 점이 많습니다 ㅜㅜ
제가 궁금한건, 혹시 테스트데이터 같은 경우 어느 정도의 범위로 얼마나(데이터 개수라 해야하나요?) 만들어 놓으시는지 궁금합니다.
예를들어
https://www.acmicpc.net/proble... (구간 합 구하기) 이 문제 같은 경우에
N, M, K의 수많은 조합이 생길 수 있잖아요?
이때 모든 N에 대해 몇개씩 데이터를 만든다거나, 특정한 N들(ex) 1, 50, 100, 150, ..., )에 대해서만 몇 개씩 만든다거나
아니면 다른 기준이 있을까 해서 질문드립니다
감사합니다!