[프로그래머스] Lv2 점프와 순간이동 / JAVA

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

프로그래머스

 

---

코드

import java.util.*;

public class Solution {
    public int solution(int n) {
        /*
        44 -> 22, 11-10, 5-4, 2, 1, 0
        while(n>2)
            n을 2로 나눈다.
            나머지가 2로 나누어 떨어지는 지 확인한다.
             o : 처음으로
             x : 카운트1 증가, 나머지-1 가지고 처음으로
        */
        int ans = 1;
        while(n>2){
            if(n%2==0){
                n/=2;
            }
            else{
                n=n-1;
                n/=2;
                ans++;
            }
        }

        return ans;
    }
}

처음 문제를 읽어보고 멘붕했다.

전혀 감이 오지 않았다.

"최대공약수나 최소공배수를 쓰는 등의 수학적 공식을 찾는건가?", "어떠한 규칙도 안보이는것 같은데..."

그러면서 예시를 통해 규칙성을 찾으려는 노력을 계속 해봤다.

그러다가 결국 n부터 2로 나눈 몫들을 2로 나누어떨어지는지 확인하여, 나누어떨어지지 않을 때 마다 1씩 점프해주면 정답을 구할 수 있다는 것을 깨달았다.

 

어느 순간 갑자기 해답이 보이게 되어 조금은 신기한 문제였다.

20분 정도 소요되었다.