[JAVA] 프로그래머스 : 점프와 순간 이동 (Summer/Winter Coding(~2018))

programmers.co.kr/learn/courses/30/lessons/12980?language=java

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

해결 방안

 처음에는 문제에서 제시된 해결 방안을 보고 탐색을 이용한 최소 값을 구하려고 하였으나 depth가 정해져 있지 않고 입력으로 주어진 n이 10억이 넘는 것을 보고 다른 방법을 생각해보게 되었다.

n이 정해져 있고 최소 건전지 사용량도 정해져 있다고 생각하게 되었고 문제에서 주어진 5와 6을 이용해 가장 좋은 방법을 생각해보았다.

그 후 n을 이용하여 거꾸로 계산하였다.
짝수일 때 2로 나누고 홀수이면 1을 빼서 다시 돌려본 결과 거꾸로 계산을 하게 되면 stack에서 나중에 계산한 것이 처음 나오는 것처럼 답을 구할 수 있다고 생각하게 되었다.

그 생각에서 나온 코드이다.

 

코드

import java.util.*;

// 점프와 순간 이동
// k칸 앞으로 점프 - k만큼 건전지 소모
// 현재까지 온 거리 x 2 - 건전지 소모 x
// 건전지 사용량을 줄이기 위해 점프 최소

// 사용해야 하는 건전지 사용량 최솟값 return
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;
    }
}