푼 사람 적은 실버길래 몇 시간 동안 확장 유클리드 알고리즘까지 고민하다가 에라 모르겠다하고 브루트포스로 내고 맞아서 질문드립니다.

T가 최대 100이고 a, b가 1만까지면 최악의 경우 O(a * b * T)로 100억회라 터질 것 같은데 별로 안 걸려서 궁금합니다. 조건에 맞는 수열 생성기가 아니면 몇 개 체크 안하고 넘어가서 되는 건가요? 아니면 a=9997, b=9999, T=100 같은 데이터가 없어서 그런가요?

wizardrabbit   11달 전

$a$, $b$는 몰라도, $T$가 꽤 많은 케이스에서 값이 불일치하는 경우가 많아 꽤 빠르게 루프문에서 나가집니다. $T$개의 케이스에 대해 조건을 모두 만족하는지 확인하는 과정에서 하나라도 일치하지 않는다면 나머지 케이스들은 확인할 필요가 없죠.

그래서 불일치를 발견하는 순간 루프문을 빠져나가도록 최적화가 잘 된 코드는 의외로 빠른 시간에 통과하지만, 루프문에서 나가지 않고 순수하게 $T$회를 다 반복하는 코드는 정말로 시간복잡도가 $O(abT)$가 되는지라 그대로 시간초과가 됩니다.

okgo2026   11달 전

데이터 추가를 해서 더 빡빡하게 테스트를 하도록 하면 되지 않을까요?

djm03178   11달 전

데이터가 지문에 주어진 방식을 통해서만 만들어짐을 보장하는 문제이기 때문에 임의의 테스트를 100개 반복할 수는 없습니다.

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