흙금이네 블로그

아이디어 에라토스테네스의 체로 소수를 판정하고, 메모이제이션을 사용하여 시간을 단축한다. 풀이 예전에 작성한 코드가 재채점 후 시간 초과가 되어 다시 풀어본 문제로, 메모이제이션이나 불필요한 과정을 생략하여 실행 시간을 줄여야 했다. 에라토스테네스의 체로 소수인 수의 인덱스는 True, 소수가 아닌 수의 인덱스는 False로 하는 리스트 p를 만든다. 이때 입력으로 주어지는 짝수 정수를 두 홀수 소수의 합으로 나타내면 되므로 홀수이면서 소수가 아닌 수만 확인한다. 따라서 i는 3부터 시작하여 2만큼 건너뛰고, j는 i*3에서 짝수 크기만큼 건너뛰어 홀수 인덱스만 확인하도록 한다. 메모이제이션을 위해 딕셔너리 memo를 만들고, n이 0이 아닐 때까지 while문을 반복한다. n이 memo에 존재하면 그대..