[java] 프로그래머스 - 점프와 순간이동

문제

프로그래머스-점프와 순간이동
아이언 슈트를 입고 0에서 N까지 이동할 때 최소 건전지 소모량를 구하는 문제.
이동방법
(1) 현재위치 k칸에서 m칸 앞으로 가는 점프 방법(건전지 소모 : m)
(2) k*2칸으로 가는 순간이동 방법(건전지 소모 : 0)

• 예시
  목적지 : 5
  0에서 5칸으로 점프하기 : 5회
  0에서 1칸으로 점프(1) -> 2로 순간이동 -> 4로 순간이동 -> 5로 점프(1) : 건전지 소모량 2
  0에서 2칸으로 점프(2) -> 4로 순간이동 -> 5로 점프 (1) : 건전지 소모량 3
  0에서 5까지 최소 건전지 소모량은 2이다

풀이

• 제한 사항
  목적지 N : 1이상 10억 이하의 자연수

처음에 어렵게 생각해서 고생했던 문제 ㅠㅠ
memo배열을 두고 건전지 소모량을 저장하며 dp(dynamic programming)로 풀려고 했는데 풀다보니 너무 어렵게 생각하고 있는 나 자신을 발견.. (!)
최소의 소모량으로 목적지에 도달하는 방법은 순간이동이므로 이를 활용해서 구하면 간단하게 구할 수 있는 문제였다

목적지가 10이라고 하면 10의 절반은 5다 (5에서 순간이동으로 10에 올 수 있음)
5의 절반은 2지만 2로 갈려면 1회의 건전지소모가 필요하다
소모 1을 해서 2로 이동한다
2의 절반은 1이다
1은 0에서 1회 점프해서 올 수 있다
총 2회의 건전지 소모량으로 도착할 수 있다

👤👥👤👥👤 : ???

현재 위치에서 반으로 나눠가며 순간이동을 하고
짝수가 아닌경우는 -1해서(점프 1회) 반으로 나눠가며 순간이동을 한다
반복하다가 0을 만나면 순간이동만으로 목적지에 도착할 수 있다는 뜻이다
1을 만나면 0까지 점프 1회 해야하므로 점프횟수를 1 추가한다

소스코드

public class Solution {
 	static int cnt;
	public int solution(int n) {
		cnt = n;
		getMinDist(n, 0);
		return cnt;
	}

	private void getMinDist(int num, int steps) {
		if(num==0) {
			cnt = Math.min(cnt, steps);
			return;
		}else if(num==1 || num==2) {
			cnt = Math.min(cnt, steps + 1);
			return;
		}
		if (num % 2 == 0) {
			getMinDist(num / 2, steps);
		} else {
			getMinDist(num / 2, steps + 1);
		}
	}
}