개인적으로 이런 문제가 정말 어렵다. 문제를 처음 훑어봤을 때 BOJ 숨바꼭질 유형의 문제라고 생각했고 BFS, DFS를 적용해보려 노력했지만
따라서 불가능했다. 그러던 중 배터리를 최소로 사용해야함에 집중해서 다시 생각해봤다. 그렇다면 순간이동을 최대한 많이 사용하고 점프를 최소로 사용해야했다. 그리고 문제를 다시 읽으며 중요점을 체크했다.
그리고 이전에 풀었던 문제 BOJ A->B에서 bottom-up
보다는 top-down
방식이 경우의 수가 훨씬 줄어드는 것이 떠올라 대입해봤다.
정리하자면
몇 칸 점프를 할 것인가
또는 순간 이동할 것인가
의 많은 경우의 수를 현재 N이 짝수인가 홀수인가
의 두 가지 경우의 수로 줄일 수 있었고 bottom-up
에서 N을 넘는 경우를 생각해야했다면 top-down
에서는 0보다 작아지는 경우가 없기 때문에 생각할 필요가 없었다.
import java.util.*;
public class Solution {
public int solution(int n) {
int ans = 0;
while(n != 0){
if(n % 2 == 0){
n /= 2;
} else {
n--;
ans++;
}
}
return ans;
}
}