[코딩테스트 연습] 점프와 순간이동

 

문제: https://programmers.co.kr/learn/courses/30/lessons/12980

---

N이 10억이하의 자연수이므로 BFS 탐색을 하면 그대로 터지는 문제입니다.

 

순간이동은 공짜이므로 순간이동을 가장 많이 한다면 그 값이 최소비용이 될 것입니다.

 

그러면 주어진 수에서 점프하는 거리를 최대로 줄이다 보면 1을 초과하는 거리는 점프를 할 필요가 없습니다.

 

즉, 주어진 수를 이진수로 나타내면 1로 나타나는 지점이 어쩔 수 없이 점프를 해야하는 지점입니다.

 

그러니 이진수를 만든 후 거기서 1의 개수를 세면 그게 최소비용이 됩니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter01.cc