n이 너무 큽니다. 필요한 부분만 탐색해보는 것은 어떨까요?
27440번 - 1로 만들기 3
너비 우선 탐색(BFS)의 개념을 찾아보시는 걸 추천드립니다.
자연수 i를 1로 만드는 데 몇 회의 연산이 필요한지를 계산하는 것(DP 풀이)이 아니라 1부터 시작하여 k번의 연산으로 무슨 수에 도달할 수 있는지를 모두 탐색하면(BFS) 문제를 빠르게 풀 수 있습니다.
이 문제를 DP로 풀지 못하는 이유는 입력 조건 때문입니다. DP 풀이의 시간 복잡도와 공간 복잡도는 모두 O(N)이므로 N이 최대 10^18이라는 조건 하에서는 DP로 풀 수 없습니다.
not i+1 in visited
이 문장은 모든 원소를 순회하면서 없는지 조회하기 때문에 최악의 경우에 O(N)의 시간이 걸리게 됩니다. 따라서 딕셔너리를 사용하는 것을 권장합니다. 딕셔너리에서 in은 대략 O(1)의 시간(아닐 때도 있습니다.)에 작동합니다.
또한 구현 부분에서 아마도 너비 우선 탐색을 구현하신 것 같은데 제 생각이 맞다면 잘못 구현되어 있습니다. 너비 우선 탐색은 큐를 사용하는데 파이썬 리스트는 기본적으로 스택이라고 이해하심이 좋습니다. 저는 너비 우선 탐색을 구현할 때 collections 라이브러리에서 deque를 사용합니다.
deque와 queue는 검색을 통해 공부하시는 편이 더 나을 것이라고 생각합니다.
댓글을 작성하려면 로그인해야 합니다.
1234juwon 1년 전
최대한 시간 줄이려고 defaultdict랑 readline 까지 써봤는데 계속 시간 초과가 뜨네요ㅠㅠ. 어떻게 고치면 될까요?