백준 1904번
https://www.acmicpc.net/problem/1904

문제

---

생각하기

---

• DP문제이다
  • 메모이제이션을 사용해야 한다.
  • Top-Down, Bottom-Up 2가지로 구현이 가능하다.
• 반복되는 규칙으로 인해서, 이전의 값의 영향을 받는 환경이기 때문에 메모이제이션을 쓰기 적합하다.

동작

문제의 로직은 그냥 간단하다. N번째의 값을 구하고 싶다면 (N-1) + (N-2)의 값을 구하면 된다.
이 규칙의 반복이기 때문에 어렵지 않다.

		if (N == 1) {
			return 1;
		} else if (N == 0) {
			return 0;
		} else if (N == 2) {
			return 2;
		}

		if (memo[N] == null) {
			memo[N] = (DP(N - 1) + DP(N - 2)) % MOD;
		}

Top-Down 구현은 재귀를 통해 아래로 내려왔을 때, N값이 0, 1, 2 가 됬을 경우에는 return 의 해당 값을 돌려주도록 했다.

이렇게 아래로 내려오면서 memo[]의 각 배열에 수가 저장되어 쌓이게 되면서 가지치기를 하게되고, 효율을 끌어올릴 수 있다.

하지만, 아무래도 모든 경우에서 위에서 출발하다 보니 N의 값이 높을 경우에는 아래를 찍고 올라오면서 시간이 많이 걸릴 수 밖에 없는 것 같다.

        memo[0] = 0;
        memo[1] = 1;
        memo[2] = 2;


	// Bottom-Up
    private static int DP(int N) {
        for(int i=3; i<=N; i++) {
            memo[i] = (memo[i-1] + memo[i-2]) % MOD;
        }

        return memo[N];
    } // End of DP

Bottom-Up에서는 재귀를 통해 return을 하는 것이 아니기 때문에 바깥에서 미리 memo배열에 0, 1, 2의 값을 저장하고 실행한다. 이렇게 되면 0, 1, 2는 반복문에서 제외를 해도 되고 3을 구할 때도 이전의 값을 알고 있기 때문에 하나씩 쌓아 올리면서 정답을 찾아나가면 된다.

Bottom-Up

Top-Down

시간은 확실히 바텀업이 빠르긴한데 2가지 방법을 모두 구현할 줄 아는 것이 중요하다고 생각하기 때문에 DP를 풀때는 꼭 2가지를 모두 구현하고자 한다.

코드

---

Java

Top-Down

import java.io.*;
import java.util.*;

public class Main {
	private static final int MOD = 15746;
	static Integer memo[] = new Integer[1000001];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		System.out.print(DP(N));
	} // End of main

	private static int DP(int N) {
		if (N == 1) {
			return 1;
		} else if (N == 0) {
			return 0;
		} else if (N == 2) {
			return 2;
		}

		if (memo[N] == null) {
			memo[N] = (DP(N - 1) + DP(N - 2)) % MOD;
		}

		return memo[N];
	} // End of DP
} // End of Main class

Bottom-Up

import java.io.*;

public class Main {
    private static final int MOD = 15746;
    static int memo[] = new int[1000001];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        memo[0] = 0;
        memo[1] = 1;
        memo[2] = 2;
        System.out.print(DP(N));
    } // End of main

	// Bottom-Up
    private static int DP(int N) {
        for(int i=3; i<=N; i++) {
            memo[i] = (memo[i-1] + memo[i-2]) % MOD;
        }

        return memo[N];
    } // End of DP
} // End of Main class