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

문제출처

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

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

문제풀이

이런 문제는 계속 예제를 만들고 시뮬레이션을 돌리며 규칙을 찾아야 하는거 같다. 시간도 많이 잡아먹고 어렵게 느껴진다 ㅠ

문제에서 주어진대로 위치 0에서 n까지 가는 구조로 하다보니 규칙을 찾기 어려웠다. 그래서 n에서 0으로 가는 구조로 다시 생각해봤다. 문제를 풀때 핵심 키워드로 작용한 내용은 순간이동에 대한 조건이다. (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동

즉, 순간이동을 하면 짝수가 된다는 점에서 짝수와 홀수간 규칙이 있지 않을까 의심해봤다. 짝수인 경우 순간이동을 하고 홀수인 경우 1칸만 점프하면 배터리 사용량을 최소화 할 수 있다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%A0%90%ED%94%84%EC%99%80%20%EC%88%9C%EA%B0%84%EC%9D%B4%EB%8F%99.java

sw93/algorithm

 

import java.util.*;
/**
* k칸 앞으로 점프 || 현재까지 온거리 * 2
* k칸 점프시 건전지 사용
* n만큼 떨어져 있는 곳으로 이동할 때 건전지 사용량을 최소로하는 값 return
* top - down 방식으로 풀이
*/
public class Solution {
    public int solution(int n) {
        int ans=0;
        while (n > 0) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                ans++;
                n -= 1;
            }
        }
        return ans;
    }
}

 

 

문제를 다 풀고 다른사람 풀이를 찾아보는 중에 생각지도 못한 방법이 있었다. 비트를 사용하는 방법인데 자세한 설명은 아래 블로그를 참조하면 된다.

public int solution(int n) {
	return Integer.bitCount(n);
}

출처 : https://taesan94.tistory.com/142