DP 기초: 피보나치 수 2748, 1로 만들기 1463 Java

1) 피보나치 수 https://www.acmicpc.net/problem/2748

2) 1로 만들기 https://www.acmicpc.net/problem/1463

 

1) 피보나치 수

간단히 푸는 방법도 있는데 해당글을 참고해서 DP 방식으로 풀어보았다

DP는 반복되는 문제는 한 번만 풀어야 하는데(메모제이션) 그냥 풀면 DP 방식이 아닌것 같다

public class baekjoon_2748 {
    static int N;
    static int count = 0;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];

        arr[0] = 0;
        arr[1] = 1;

        int result = dp(N);
        System.out.println(result);
    }

    public static int dp(int n) {
        if(n == 0) return arr[0];
        if(n == 1) return arr[1];

        if(arr[n] == 0) {
            arr[n] = dp(n-1) + dp(n-2);
        }
        return arr[n];
    }
}

 

2) 1로 만들기

!!

처음 보면 아래 함수가 이해하기 쉽다

int recur(int n, int count) {
    if (n == 1) return count;

    int result = Integer.MAX_VALUE;
    if (n % 3 == 0) result = Math.min(result, recur(n / 3, count + 1));
    if (n % 2 == 0) result = Math.min(result, recur(n / 2, count + 1));
    result = Math.min(result, recur(n - 1, count + 1));

    return result;
}

그런데 다른 코드를 보면 아래와같이 하곤 한다

return Math.min(recur(N / 2, count + 1 + (N % 2)), recur(N / 3, count + 1 + (N % 3)));

이는 최적화한것으로,

count + 1 + (N%2) 부분에 '-1을 뺀다는 동작'이 담겨있는 것이다

나누기가 안될 경우 (나머지가 나올 경우) -1을 뺀 동작을 했다고 치고 count에 더해주는 것이다 (N%2, N%3) 부분