1234juwon   1년 전

최대한 시간 줄이려고 defaultdict랑 readline 까지 써봤는데 계속 시간 초과가 뜨네요ㅠㅠ. 어떻게 고치면 될까요? 

jun83   1년 전

n이 너무 큽니다. 필요한 부분만 탐색해보는 것은 어떨까요?

1234juwon   1년 전

그런데 a[n]을 알려면 a[n-1]을 알아되지 않나요? 결국은 다 구해야 되는 것 아닌가요?

not_strober   1년 전

너비 우선 탐색(BFS)의 개념을 찾아보시는 걸 추천드립니다.

자연수 i를 1로 만드는 데 몇 회의 연산이 필요한지를 계산하는 것(DP 풀이)이 아니라 1부터 시작하여 k번의 연산으로 무슨 수에 도달할 수 있는지를 모두 탐색하면(BFS) 문제를 빠르게 풀 수 있습니다.

이 문제를 DP로 풀지 못하는 이유는 입력 조건 때문입니다. DP 풀이의 시간 복잡도와 공간 복잡도는 모두 O(N)이므로 N이 최대 10^18이라는 조건 하에서는 DP로 풀 수 없습니다.

jun83   1년 전

생각보다 적은 연산으로 1에 도달할 수 있습니다. 모든 경우를 탐색하더라도 너비 우선 탐색의 경우 연산의 횟수가 적은 경우의 수부터 탐색하므로 모든 경우를 탐색하기 전에 1에 도달합니다.

추가로 자연수 i를 1로 만드는데 몇 회의 연산이 필요한지 계산하는 방식의 풀이도 가능합니다. 저 같은 경우는 그렇게 해결했습니다. 또한 dfs도 충분히 가능한 문제입니다.

1234juwon   1년 전

도와주셔서 정말 감사드립니다^^. 그런데 계속 시간 초과가 떠서ㅠㅠ 어떻게 고치면 될까요?(참고로 전 중학생입니다)

coxld   1년 전

list에서 in 연산은 시간복잡도가 O(N)입니다. set을 배워보세요

jun83   1년 전

not i+1 in visited
이 문장은 모든 원소를 순회하면서 없는지 조회하기 때문에 최악의 경우에 O(N)의 시간이 걸리게 됩니다. 따라서 딕셔너리를 사용하는 것을 권장합니다. 딕셔너리에서 in은 대략 O(1)의 시간(아닐 때도 있습니다.)에 작동합니다.

또한 구현 부분에서 아마도 너비 우선 탐색을 구현하신 것 같은데 제 생각이 맞다면 잘못 구현되어 있습니다. 너비 우선 탐색은 큐를 사용하는데 파이썬 리스트는 기본적으로 스택이라고 이해하심이 좋습니다. 저는 너비 우선 탐색을 구현할 때 collections 라이브러리에서 deque를 사용합니다. 

deque와 queue는 검색을 통해 공부하시는 편이 더 나을 것이라고 생각합니다.

coxld   1년 전

BFS를 수행할 때 1에서 n을 향해 탐색하지 말고 n에서 1을 향해 탐색하도록 바꿔보세요.

1234juwon   1년 전

덕분에 해결되었습니다^^. 정말 감사드립니다!

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