1) 기본 실행 횟수
코드 방식을 바꾸는 게 유일할 것 같습니다. 현재 출력 방식은 전혀 시간을 잡아먹지 않습니다.
문제는 n=3*2^10~3000일 때,
for문 range(n)에 range(2*n-1)이니
2*n^2의 횟수만큼 확인할 것이고, 이는 현재 코드 방식과 같이, 각 셀 별로 확인하는 어떤 방식이라도 기본으로 깔아야겠죠.
그러면 대략 1.8*10^7회이죠.
이건 문자열의 개수와도 일치하기 때문에 어떤 코드라도 기본으로 깔고 가는 횟수입니다. 문제는 현재 코드에 의해 추가로 곱해지는 상수입니다.
2) 문제점
위 횟수에 더해 c(y,x)의 while문은 t가 2로 나눠지는 것을 최대 10번 반복하고,
그 안에 있는 여러 조건문을 확인하는 건 대략 2-3번쯤 곱하는 효과일까요. 거기에 반복문 밖은 조건문은 2-3을 더하는 효과 정도니 대략 30정도 증폭.
그러면 최대 5.4*10^8이니까 상당한 횟수입니다.
시간 제한이 1초인데, 파이썬의 1초는 대략 10^7~8.5정도의 횟수를 커버할 수 있음을 생각하면 거의 성공의 상한선인 것 같습니다.
3) 메모리와 python특, 그리고 답
이 부분이 성공의 상한선에서 실패로 가는 부분인 듯합니다. 현재 코드에서는 리스트 생성, 함수 실행과 횟수가 많은 점 등, 새로운 요소를 반복적으로 생성하는 것 자체도 문제입니다. 이러면 메모리를 많이 잡아먹게 되는데, (경험적으로) PyPy3보다 파이썬은 메모리에 민감하기 때문에 시간에도 영향을 줄 수 있습니다. 때문에 새로운 요소를 만드는 것을 피하고, 기존 요소를 재활용하는 이 문제의 태그 '재귀'에 영향을 맞춘다면 해결 가능할 것입니다.
4) 실행 기반 확인
개인 pc로 실행해봤는데 정답 예시와는 시간이 크게 차이 나지 않더군요. 따라서 3)의 문제가 맞는 듯합니다. 그리고 pypy3로 제출하면 정답 처리가 실제로 되는 것도 확인됩니다.
5) 다른 방안
만약 모든 y,x 쌍에 대한 c(y,x)의 결과를 매번 함수 실행으로 구하는 대신 DP와 같이, 기존에 구한 일부 c(y,x)로부터 간단한 조건문으로 점화적으로 구할 수 있다면 약간의 완화 효과가 예상됩니다. 하지만 그런 코드 짜기가 오히려 귀찮을 것 같네요.

ohseojun0701 1년 전
각 좌표별로 별이 찍히는지, 공백이 찍히는지 판별하는 함수를 만들어 풀려고 하였는데, 답은 맞는 듯 한데 시간이 문제입니다.
질문글들을 참고하여 출력 방식도 바꿔보았지만 시간초과가 해결되지 않았습니다. 코드 방식을 수정해야 할까요?