jeonggu223   4년 전

문제를 풀고 나서 다른 사람의 풀이를 보다가 제출번호 39631575(python3중 가장 빠른 풀이) 의 다른 분이 푸신 소스를 읽었습니다.

그런데 해당 소스는 질문이 들어올 때 마다 펠린드롬인지 아닌지 체크하는 로직으로 되어있는 것 같습니다.

길이가 2000인 배열이 들어왔을 때 펠린드롬인지 체크하는 경우의 수를 살펴보면 이렇습니다.

길이가 0인 경우 : 2000개

길이가 1인 경우 : 1999개

길이가 2인 경우 : 1998개

...

길이가 1999인 경우 : 1개

이런식으로 따져보면 200만개의 경우의 수가 나옵니다. 

이는 질문의 개수가 100만개이니 질문이 겹치지 않게 100만개를 만들 수 있습니다.

겹치지 않는 질문의 100만개를 최악의 경우로 따져보면 길이가 1999 ~ 1414까지 질문의 리스트를 만들 수 있습니다.

제가 말씀드린 코드를 기준으로 하면 연산량이 1999 * 1 + 1998 * 2 ... 1414 * 587 = 10억번정도의 연산량이 나올 것 같은데 왜 가장 빠르게 통과하는 것일까요..?

테스트케이스가 부족한 건지, 제 이해가 잘못 된건지 궁금합니다.

eric00513   4년 전

안녕하세요. 말씀하신대로 해당 코드는 시간 초과가 나는 것이 맞습니다.

이에 대해 데이터 추가 요청을 했습니다.

https://www.acmicpc.net/board/...

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