프로그래머스 점프와 순간 이동 JAVA

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

문제

해당 문제는 도착 지점이 주어졌을 때 0에서 해당 지점까지 몇의 건전지를 사용하여 갈 수 있는지 구하는 문제다.

• 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
• 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
• 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.

조건

• 숫자 N: 1 이상 10억 이하의 자연수
• 숫자 K: 1 이상의 자연수

풀이

해당 문제는 처음에 bfs를 이용하면 되겠다 생각했다. 백준에 있는 숨바꼭질 문제와 비슷해 보였고 bfs를 이용해서 0에서부터 앞으로 나아가며 도착하면 리턴하는 식으로 문제를 해결했더니 효율성에서 모두 실패하였다. 

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
static int[] arr;
    public static int solution(int n) {
        arr = new int[n+1];
        for (int i = 2; i < arr.length; i++) {
			arr[i] = Integer.MAX_VALUE;
		}
        bfs();
        return arr[n];
    }
	private static void bfs() {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(1);
		arr[1] = 1;
		while(!q.isEmpty()) {
			int n = q.poll();
			if(n == arr.length-1) {
				return;
			}
			if(n+1 < arr.length && arr[n]+1<arr[n+1]) {
				q.add(n+1);
				arr[n+1] = arr[n]+1;
			}
			if(n*2 < arr.length && arr[n]<arr[n*2]) {
				q.add(n*2);
				arr[n*2] = arr[n];
			}
		}
	}
}

 

Baekjoon 1697 숨바꼭질 JAVA

 

이후 질문하기를 참고하다 보니 0에서 도착으로 접근이 아닌 도착에서 0으로 접근하라는 힌트를 얻을 수 있었고, 생각해보면 도착에서 2로 나눠지면 나누고 아니면 -1을 한 뒤 2로 나누는 방식으로 0에 도착할 수 있고 -1을 한경우에만 1씩 카운트하면 문제를 해결할 수 있다.

코드

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

 

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드