10942번 - 팰린드롬?
문제를 풀고 나서 다른 사람의 풀이를 보다가 제출번호 39631575(python3중 가장 빠른 풀이) 의 다른 분이 푸신 소스를 읽었습니다.
그런데 해당 소스는 질문이 들어올 때 마다 펠린드롬인지 아닌지 체크하는 로직으로 되어있는 것 같습니다.
길이가 2000인 배열이 들어왔을 때 펠린드롬인지 체크하는 경우의 수를 살펴보면 이렇습니다.
길이가 0인 경우 : 2000개
길이가 1인 경우 : 1999개
길이가 2인 경우 : 1998개
...
길이가 1999인 경우 : 1개
이런식으로 따져보면 200만개의 경우의 수가 나옵니다.
이는 질문의 개수가 100만개이니 질문이 겹치지 않게 100만개를 만들 수 있습니다.
겹치지 않는 질문의 100만개를 최악의 경우로 따져보면 길이가 1999 ~ 1414까지 질문의 리스트를 만들 수 있습니다.
제가 말씀드린 코드를 기준으로 하면 연산량이 1999 * 1 + 1998 * 2 ... 1414 * 587 = 10억번정도의 연산량이 나올 것 같은데 왜 가장 빠르게 통과하는 것일까요..?
테스트케이스가 부족한 건지, 제 이해가 잘못 된건지 궁금합니다.
안녕하세요. 말씀하신대로 해당 코드는 시간 초과가 나는 것이 맞습니다.
이에 대해 데이터 추가 요청을 했습니다.
https://www.acmicpc.net/board/...
댓글을 작성하려면 로그인해야 합니다.
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억번정도의 연산량이 나올 것 같은데 왜 가장 빠르게 통과하는 것일까요..?
테스트케이스가 부족한 건지, 제 이해가 잘못 된건지 궁금합니다.