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

문제 설명

 

프로그래머스

 

접근 방법

처음 해당 문제에 어떤 방법으로 접근해야할지 고민이 많았습니다.

 

그리디 → 백트래킹 → 메모이제이션 → 숫자 규칙

 

처음에는 그리디 알고리즘 느낌으로 순간 이동으로 최대한 많이 이동함으로써 배터리를 이용한 이동횟수를 최소화하고 나머지 이동 칸수에 대해서만 배터리를 이용하여 1칸씩 전진하는 방법을 취할려고 했었으나, 특정 경우의 수에선 순간 이동 중에 배터리를 사용하여 한 칸 전진한 후 다시 순간 이동하는 것이 최적의 해인 경우가 존재했기 때문에 그리디 알고리즘으로 구현하기는 다소 어렵겠다는 생각이 들었습니다.

 

이후 백트래킹을 통해 모든 경우의 수를 고려해볼까도 생각했었습니다. 하지만 n은 최대 10억이라는 수로 배터리를 이용한 이동과 순간 이동을 조합한 경우의 수를 고려하다가는 엄청난 시간이 소요될 것이라 판단이 들어 적합하지 않곘다는 생각이 들었습니다.

 

또한 메모이제이션 기법을 이용할까도 생각했었지만, n = 1, n = 2, n = 3 등 각각의 경우의 수에 대해 최적의 해 값이 늘어나는 패턴도 아니라 오히려 들쭉날쭉한 패턴이라 어떠한 점화식을 세우기도 힘들겠다는 생각이 들었습니다. 무엇보다 n이 최대 10억이기 때문에 이렇게 큰 배열을 선언했다가는 OutofMemoryError 에러가 발생합니다.

 

그래서 해당 문제는 일종의 숫자의 규칙을 찾는 문제라고 생각했습니다. 우선은 n = 1, n = 2, n = 3 등 각각의 경우의 수와 그 최적의 해의 값의 관계를 분석해보기로 했습니다.

 

일단 n = 1일 때 최초 배터리로 한 칸 이동 후 순간이동을 계속하면 n의 값이 1, 2, 4, 8, 16, .. 수들에 대해선 모두 배터리가 1만큼 소요되는 것을 생각해봤고 이후에는 n을 2진수의 형태로 나타내보면 뭔가 보이지 않을까도 했습니다.

 

 

이렇게 나타내보니 n의 값과 그에 대한 최적의 해의 값인 k의 관계에 있어서 무언가 규칙이 존재하는 것을 발견할 수 있었습니다. 바로 1 비트의 개수가 k의 값이라는 것입니다.

 

앞서 n의 값이 1, 2, 4, 8, 16, .. 수들에 대해선 모두 배터리가 1만큼 소요된다는 것을 생각했었다고 했습니다. 이때 이 값들의 특징은 모두 2진수라는 점이었습니다. 그리하여 n이라는 숫자를 2진수로 나타냈을 때 실질적으로 2진수를 구성하는 1 비트의 개수만큼 배터리를 이용해 한 칸씩 이동하면 나머지 이동분에 대해서는 순간 이동으로 이동할 수 있지 않을까 직관적으로 추론해볼 수 있었습니다.

 

나의 소스 코드

public class Solution {
    
    public int solution(int n) {
        int battery = 0;
        String s = Integer.toBinaryString(n);
        for (char bit : s.toCharArray()) {
            if (bit == '1') {
                battery++;
            }
        }

        return battery;
    }
}

 

참고자료

• https://school.programmers.co.kr/learn/courses/30/lessons/12980