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

문제

---

생각하기

---

• DP 문제이다.

• 메모이제이션을 사용해서 TopDown으로 구현했다.

  • 1, 2, 3을 사용하는 과정에서 '다른 값을 선택한다' 와 '선택하지 않는다' 2가지의 방향으로 진행하면 된다.

동작

    private static int topDown(int n, int m, int currentNumber) {
        if (n == 0 && m == 0) return 1;
        if (n < 0 || m < 0 || currentNumber <= 0) return 0;

        if (memo[n][m] != -1) return memo[n][m];

        memo[n][m] = (topDown(n - currentNumber, m - 1, 3) + topDown(n, m, currentNumber - 1)) % MOD;

        return memo[n][m];
    } // End of topDown()

TopDown으로 N과 M의 값으로 시작해서 아래로 내려간다.

값을 선택하지 않고 그대로 진행하는 경우, topDown(n - currentNumber, m - 1, 3)으로 n을 선택한 값 만큼 빼주고, m의 사용횟수도 1을 빼준다.

값을 변경하고 사용하지 않는 경우, topDown(n, m, currentNumber - 1)로 currentNumber만 그대로 -1을 해준다.

결과

코드

---

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static final int MOD = 1_000_000_009;
    private static int N, M;
    private static int[][] memo = new int[1001][1001];

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for (int[] t : memo) {
            Arrays.fill(t, -1);
        }

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            input();
            bw.write(solve());
        }

        bw.close();
    } // End of main

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        sb.append(topDown(N, M, 3)).append('\n');
        return sb.toString();
    } // End of solve()

    private static int topDown(int n, int m, int currentNumber) {
        if (n == 0 && m == 0) return 1;
        if (n < 0 || m < 0 || currentNumber <= 0) return 0;

        if (memo[n][m] != -1) return memo[n][m];

        memo[n][m] = (topDown(n - currentNumber, m - 1, 3) + topDown(n, m, currentNumber - 1)) % MOD;

        return memo[n][m];
    } // End of topDown()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
    } // End of input()
} //  End of Main class