이 문제는 대전 예선 문제로, 실제 대회에서 O(K^3)이 통과했으며, 많은 팀이 해결한 문제입니다.
한때 대전 대회가 테스트케이스의 개수를 명시하지 않고 멀티테케 문제를 내던 시절이 있었는데, 그 당시 그냥 테스트케이스가 하나라는 가정 하에 통과될 복잡도의 솔루션을 내면 통과하는 경우가 대부분이었고, 그 상황을 반영하여 만든 데이터로 보입니다.
실제 대회 환경에 적합하게끔 놔 두는 것이 맞아 보이네요.
https://www.acmicpc.net/proble...
물론 O(K^2) 솔루션도 존재하는 문제이기 때문에, 변형판이 BOJ에 올라와 있습니다.
O(K^2)을 요구하는 문제는 위의 문제입니다.
thak00 5년 전
일단 테스트케이스가 최대 몇개가 주어지는지 T에 대한 조건이 없습니다.
저의 풀이는 K^3 풀이입니다. 2초 내에 한두개의 케이스는 무난하게 통과가 되겠지만 테스트케이스가 많아진다면 당연히 시간초과가 나야 할 코드지만 시간초과가 나지 않습니다.
시간초과가 나거나 혹은 테스트케이스의 수가 적어 나오지않는것이라면 테스트케이스에 대한 조건을 추가해주시기 바랍니다.