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

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

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

풀이과정

N의 값에 따라 어떤 방식으로 이동하는지 살펴보면 다음과 같은 표를 얻을 수 있다.

N	이동방법 (J: Jump, TP: Teleport)		K
1	J(0 → 1)		1
2	J(0 → 1) → TP(1 → 2)		1
3	J(0 → 1) → TP(1 →2) → J(2 → 3)	N(2) 까지 이동 후 1칸 점프	2
4	J(0 → 1) → TP(1  →2) → TP(2  →4)	N(2)까지 이동 후 TP	1
5	J(0 → 1) → TP(1  →2) → TP(2  →4) → J(4 → 5)	N(4)까지 이동 후 1칸 점프	2
6	J(0 → 1) → TP(1  →2) → J(2 → 3) → TP(3  →6)	N(3)까지 이동 후 TP	2
7	J(0 → 1) → TP(1  →2) → J(2 → 3) → TP(3  →6) → J(6 → 7)	N(6)까지 이동 후 1칸 점프	3
8	...	N(4)까지 이동 후 TP	1
9		N(8)까지 이동 후 1칸 점프	2
10		N(5)까지 이동 후 TP	2
11		N(10)까지 이동 후 1칸 점프	3
12		N(6)까지 이동 후 TP	2

이를 통해 임의의 양의 정수 N이 주어졌을 때, N까지 이동할 수 있는 방법은 크게 두 가지로 나뉜다는 것을 확인할 수 있다.

각각의 경우에 대해 최소한의 배터리를 사용하여 이동 가능한 경우를 살펴보면 다음과 같다.

1. N이 2로 나누어 떨어질 때
   • N/2 만큼 이동한 후 텔레포트
2. N이 2로 나누어 떨어지지 않을 때
   • 1칸 이전까지의 이동방법 사용 이후 1칸 점프

이 때, 배터리 소모가 발생하는 경우는 2의 경우이다. 2의 경우가 발생할 때 마다 배터리가 1씩 소모된다.

즉, 최종 도착 위치부터 1, 2의 경우를 역으로 추적해가며 출발 위치까지 돌아가면 총 배터리 소모값을 알 수 있다.

 

이를 주어진 예시 N = 5에 적용 해 보면 다음과 같다.

1. N(5000) ← N(2500)까지 이동 후 TP ← N(1250)까지 이동 후 TP ← N(625)까지 이동 후 TP
2. N(625) ← N(624)까지 이동 후 1칸 점프 (배터리 소모 1 발생)
3. N(624) ← N(312)까지 이동 후 TP ← N(156)까지 이동 후 TP ← N(78)까지 이동 후 TP ← N(39)까지 이동 후 TP
4. N(39) ←N(38)까지 이동 후 1칸 점프 (배터리 소모 1 발생)
5. N(38) ← N(19)까지 이동 후 TP
6. N(19) ← N(18)까지 이동 후 1칸 점프 (배터리 소모 1 발생)
7. N(18) ←N(9)까지 이동 후 TP
8. N(9) ← N(8)까지 이동 후 1칸 점프 (배터리 소모 1 발생)
9. N(8) ← N(4)까지 이동 후 TP ← N(2)까지 이동 후 TP ← N(1)까지 이동 후 TP
   
10. N(1) ← 1칸 점프 (배터리 소모 1 발생) 

총 배터리 소모값 = 5

소스코드

public class Solution {
    public int solution(int n) {
        int cost = 0;
        while (n > 0) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                n--;
                cost++;
            }
        }
        return cost;
    }
}