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

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

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

2021-07-22

---

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

#문제풀이

진짜 어이없게 시간을 질질 끌었던 문제이다.

 

1억이라는 조건을 제대로 체크 안 하고 bfs로 돌렸다가, 메모리 초과를 얻었다; 

 

그래서 차근차근 그림을 그려보다가 눈치를 챘다,,,

n == 5 일 때를 기준으로 0까지 가는 프로세스들을 보면 알 수 있다.

점프는 현재 포지션이 짝수/홀수 모두 가능 하고, 순간이동은 짝수일때만 가능하다. 하지만, 점프는 최대한 덜 쓰라고 나와있어서, 홀수일때는 점프만 하고, 짝수 일 때는 순간이동만 하기로 하였다.