[Python] BOJ(백준) 16953번 - A -> B(A → B)

링크

https://www.acmicpc.net/problem/16953

난이도(solved.ac 참고)

실버1

풀이

숨바꼭질과 매우 유사한 문제이다. 그렇지만 숨바꼭질과 똑같이 풀면 메모리 초과가 뜬다. 범위가 10^9까지로 훨씬 넓기 때문이다. 그래서 count를 사용해야되는데, count를 그냥 변수로 처리하고 더해주는 방식으로 간다면 2배, 뒤에 1 붙인 모든 값에 대해 count가 더해지기 때문에 정확한 값을 도출할 수도 없다.

 

그래서 덱에 넣는 값에 count도 같이 넣었다. 그러면 몇 번째 연산인지 count로 구할 수 있다.

x에 대해 두배한 값, 또는 뒤에 1을 붙인 값이 b를 넘지만 않는다면 전부 큐에 넣어주고 반복하다가 x가 b와 같아진다면 그 x에 대한 count를 반환하면 된다.