dhunter   2년 전

일단 스포일러 검열은 해두었습니다만 지워져도 어쩔 수 없죠.

풀고나서야 깨달은건데 이 문제 '재귀' 카테고리 안에 있는거였군요 (...)

일단 처음에는 N이 작어보여서 무식하게 (...) 응답 문자열 전체를 만들고 이걸 순차적으로 빼는 루틴으로 했습니다.

만들어놓고 보니 타임아웃으로 망하는군요. 대략 O(n**2) 정도의 속도였을겁니다.

PC에서 돌려보니 0~9까지는 이렇게 만들어도 0.01초 컷인데 10은 0.15초, 11은 1.01초, 12는 24.93초로 망합니다.

그래도 일단 0~9까지 결과는 올바르게 나오니까 낮은 숫자의 출력을 보면서 경향성을 찾으려고 했습니다. 

(여기서부터는 스포일러라 검열)

그런데 여기서... '재귀' 항목을 못보고... (...)

N<=12 (약 500KB + 2배)면 메모리는 충분하지! 판단하고 그냥 N[0]부터 N[12]까지 list를 만들었습니다. (...)

대략적으로 O(n) 수준의 로직입니다.

(여기서부터는 스포일러라 검열)

결과적으로 일단 시작하자마자 0~12를 다 만들어버리고 요청 들어오면 결과문만 찍어주는 프로그램을 만들어버렸습니다.

채점 결과 보니까 아마 저랑 같은 결말에 다다르신 분도 꽤 되신거 같은데, 글이 없어서 써봅니다.

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