print가 너무 느립니다. https://www.acmicpc.net/blog/v... 를 참조하세요.

print가 빠르진 않지만 sys.stdout.write와 비교해서 수 배씩 차이가 나는 게 아니고, 기본적으로 함수 호출 비용이 높기 때문이라고 생각되네요.

print도 star도 호출 자체가 너무 많이 일어납니다.

문자열 구하는 로직을 그대로 두고 print문을 한 번만 호출하는 시간 초과 코드

https://www.acmicpc.net/source...

재귀를 할 때 메모이제이션을 하는 정답코드 

https://www.acmicpc.net/source...

메모는 하는데 출력을 그대로 한 글자씩 하는 정답코드

https://www.acmicpc.net/source...

두 함수의 차이는 생각보다 큽니다. 링크한 글을 보시면 for i in range(1,n+1): sys.stdout.write(str(i)+'\n')는 1.3722초, for i in range(1,n+1): print(i)는 3.051초로 2배 이상의 차이가 나는 것을 볼 수 있습니다. 그리고 출력하는 내용에 따라서 더 큰 차이가 나기도 합니다.

그와는 별개로 다시 보니 이 코드는 재귀 호출을 한 것이 문제가 아니라, 필요 이상으로 재귀 호출을 하게 되는 것이 문제입니다.

정해대로라면 O(n^2)번의 재귀 호출로 문제를 해결할 수 있는데, 이 코드는 각 좌표에 대해 평균 O(log(n))번의 호출을 하게 되어 총 O(n^2logn)번의 호출이 발생하게 됩니다.

http://boj.kr/a18c2409e2de4f61...와 같이 재귀 함수를 만들면 print로도 3초 내에 통과가 가능하고, http://boj.kr/44047b8696a24f14... 와 같이 sys.stdout.write를 사용하면 단 436ms만에 통과됩니다.

두 분 덕분에 깔끔하게 해결하고 많이 도움되었습니다.

출력함수의 호출비용을 생각하는 것과 메모이제이션의 아이디어 새로 머릿속에 넣고갑니다!

정말 감사합니다~~