첫 시도
import java.util.*;
/*
1.한 번에 K칸 앞으로 -> K만큼 건전지 사용
2.현재 거리 * 2 -> 건전지 사용 X
다 기록해놓음 -> 메모리 사용 초과
*/
public class Solution {
public int solution(int n) {
int ans = 0;
int curDist = 1;
while(true){
if(curDist * 2 > n)
break;
curDist = curDist * 2;
}
ans = n - curDist + 1;
return ans;
}
}일단 이 문제를 봤을 때 백준의 숨바꼭질 문제와 흡사한 느낌을 받았고 문제 해결을 위해 그림을 그렸을 때도 비슷하게 나왔다
하지만 문제에 나와 있는 조건을 보았을 때 10억까지도 나올 수 있는 상황에서 BFS를 사용해서는 효율이 좋게 나오기가 어려울 것 같았다.
계속 고민해보다가 문제를 서칭해보고 나서 안 것은
[효율성 ] Top-Down > Down-Top
이다!
나는 1부터 시작해서 쭉 올라가는 느낌으로 무조건 생각하고 접근을 했는데 이러한 최소를 구하는 문제에서는 탑다운이 더 효율적일 수 있다는 것을 알게 되었다!
- 문제에서 요구 : 최소 비용으로 이동
- 최소 비용으로 이동 = 최대한 텔레포트를 많이 이용
