4779번 - 칸토어 집합
일단 스포일러 검열은 해두었습니다만 지워져도 어쩔 수 없죠.
풀고나서야 깨달은건데 이 문제 '재귀' 카테고리 안에 있는거였군요 (...)
일단 처음에는 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를 다 만들어버리고 요청 들어오면 결과문만 찍어주는 프로그램을 만들어버렸습니다.
채점 결과 보니까 아마 저랑 같은 결말에 다다르신 분도 꽤 되신거 같은데, 글이 없어서 써봅니다.
댓글을 작성하려면 로그인해야 합니다.
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를 다 만들어버리고 요청 들어오면 결과문만 찍어주는 프로그램을 만들어버렸습니다.
채점 결과 보니까 아마 저랑 같은 결말에 다다르신 분도 꽤 되신거 같은데, 글이 없어서 써봅니다.