[12980] 점프와 순간 이동

✔ 점프와 순간 이동

[프로그래머스 12980]

문제 분석하기

처음 위치 0에서 1칸 앞으로 점프한 다음 순간이동 하면 현재까지 온 거리의 * 2 위치로 이동하게 됨

그러므로 N에서부터 0 위치로 돌아오는 경우로 바꿔 생각하여 N이 2로 나누어 떨어진다면 순간이동, 그렇지 않다면 점프하도록 함

 

예1) 5

0(0에서 N인 5까지 이동)

→ 점프해서 1 

→ 순간이동해서 2

→ 순간이동해서 4

→ 점프해서 5

 

5(N인 5에서 0까지 이동)

→ 점프해서 4

→ 순간이동해서 2

→ 순간이동해서 1

→ 점프해서 0 

 

예2) 6

6

→ 순간이동해서 3

→ 점프해서 2

→ 순간이동해서 1

→ 점프해서 0

 

예3) 5000

5000

→ 순간이동해서 2500

→ 순간이동해서 1250

→ 순간이동해서 625

→ 점프해서 624

→ 순간이동해서 312

→ 순간이동해서 156

→ 순간이동해서 78

→ 순간이동해서 39

→ 점프해서 38

→ 순간이동해서 19

→ 점프해서 18

→ 순간이동해서 9

→ 점프해서 8

→ 순간이동해서 4

→ 순간이동해서 2

→ 순간이동해서 1

→ 점프해서 0

손으로 풀어보기

1. n부터 시작해서 2로 나누어 떨어진다면 순간이동, 그렇지 않다면 점프를 하며 0까지 도달하도록 함
2. 점프한 횟수를 반환

슈도코드 작성하기

n(이동하려는 거리)
answer(건전지 사용량의 최솟값)
while(n이 1보다 크거나 같을 동안) {
    if(n이 2로 나누어 떨어진다면) 
        순간이동 가능하므로 n / 2 위치로 갱신
    else {
        점프하므로 answer 증가
        n - 1 위치로 갱신
    }
}
answer 반환

코드 구현하기

/**
 * 12980) 점프와_순간_이동
 */
public class L025_12980 {
    // n(이동하려는 거리)
    public int solution(int n) {
        // answer(건전지 사용량의 최솟값)
        int answer = 0;
        while (n >= 1) {
            // n이 2로 나누어 떨어진다면
            if (n % 2 == 0)
                // 순간이동 가능하므로 n / 2 위치로 갱신
                n /= 2;
            // n이 2로 나누어 떨어지지 않는다면
            else {
                // 점프하므로 answer 증가
                answer++;
                // n - 1 위치로 갱신
                n -= 1;
            }
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L025_12980 solution = new L025_12980();

        int n = 6;

        int result = solution.solution(n);

        System.out.println(result);
    }
}