[devmoon] 프로그래머스 - (java)점프와 순간 이동

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

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

1. 유형

재귀, 수학

 

2. 시뮬레이션

2가지 접근법

• 동적프로그래밍
• 수학

우선 DP를 이용한 풀이는 불가능. N이 10억으로 시간초과가 발생

따라서, 재귀+수학으로 풀이

 

아래와 같이 나머지가 1인 경우의 수를 세어주면 된다.

재귀 사용

3. 코드

import java.util.*;

public class Solution {
    public int solution(int n) {
        int ans = 0;
        ans = recur(n, 0);
        return ans;
    }
    static int recur(int N, int count){
        if(N==1){
            return count+1;
        }
        if(N%2==1){
            count = recur(N/2, count+1);
        }else{
            count = recur(N/2, count);
        }
        return count;
    }
}

 

4. 느낀점

처음에 n이 10억을 못 보고 DP로 품.

제한조건을 잘 읽는 연습이 필요