wjddms206   7년 전

안녕하세요. 고수님들.. 시간초과가 납니다. 정말 미치겠어요...

처음에는 queue를 사용해서 BFS로 접근 했다가, 메모리 초과가 났습니다.

고민끝에 메모리를 최대한 줄이도록 짜봤는데요, 이제는 시간 초과가 납니다.

도대체 이 문제는 어떤 식으로 접근해야 하나요?

입력의 최댓값 1000000000000000000을 해결할 방법을 알려주세요.

제발부탁드려요 고수님들 이것때문에 몇시간째 붙잡고 있는지 모르겠습니다.

1000000000000000000을 해결할 힌트라도 알려주세요 ㅠ_ㅠ_ㅠ_ㅠ 부탁드려요...

dlwodnsdl   7년 전

힌트를 드리자면 정확히 n자리인 이친수의 개수가 몇개인지 구해보세요.

wjddms206   7년 전

한번만 더 알려주십시오 ㅠ_ㅠ 

n이 1자리~19자리까지 있을 수 있고,

arr[n] = arr[n-1]+arr[n-2] 까지를 알아냈습니다.

그리고 저 식을 토대로, 입력받은 값의 자리수가 몇개인지까지 알았습니다.

그리고... 그리고 무엇을 해야하나요... ?? 

dlwodnsdl   7년 전

1을 제외한 모든 이친수는 10으로 시작하고, n자리인 이친수의 10뒤에는 n-2자리 이하의 이친수가 오게 되고 그 순서는 유지됩니다.

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