[프로그래머스] 점프와 순간

문제 URL

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

풀이

시간초과풀이

이 문제를 보는 순간 큰 문제를 작은 문제로 정의할 수 있었다. 하나의 단계에서 취할수 있는 행동은

1. k위치에 있을때 1 ~ k만큼 점프하거나
2. 순간이동 두개의 행동 중 하나를 선택할 수 있고 최적화 문제이기 때문에 전형적인 동적계획법이라고 생각했다. 하지만 문제의 크기는 10억이다.

o(n)의 복잡도를 가져도 바로 시간초과가 나는 크기다.

해결

모든 경우를 다 고려안해도 됐다.

다시말해서 순간이동하는경우는 건전지 사용량 0이 드는것에 초점을 맞춰야한다. 이전 처럼 모두 점프하는 경우를 구하지 않아도 최대한 순간이동을 사용하는 경우를 고려하면 최적의 답을 구할수있다.

• 짝수일때는 바로 순간이동 -> 에너지 0 소모
• 홀수일때는 1칸점프하고 순간이동 -> 에너지 1소모

나는 재귀를 이용해서 풀었다.

나의 풀이 (시간초과)

• 동적계획법을 이용한 풀이 ```java import java.util.*;

public class Solution { public static int solution(int n) { int[] d = new int[n+1]; for(int i=0; i<=n; i++){ d[i] = Integer.MAX_VALUE; }

    d[0]=0; d[1] = 1;
    for(int i=2; i<=n; i++){
        if(i%2==0){
            d[i] = d[i/2];
        }
        for(int j=1; j<=i; j++){
            d[i] = Math.min(d[i], d[i-j] + j);
        }
    }

    return d[n];
} } ```

나의 풀이 (통과)

package com.algorithm.algorithm;

public class Main {
    public static void main(String[] args) {
        System.out.println(solution(5000));
    }

    public static int solution(int n) {
        if (n == 1) {
            return 1;
        }

        if (n % 2 == 0) {
            return solution(n / 2);
        } else {
            return solution(n - 1) + 1;
        }
    }
}