[알고리즘 PS(DP)] (백준 9095) 1, 2, 3 더하기 자바

백준 9095 는 solved.ac 기준 Tier : silver 3

DP 문제의 핵심은 큰 문제를 작은 문제로 나누기 이며, 해당 문제에도 적용하여 문제를 풀어야 한다.

큰 문제를 작은 문제로 나누기 위해서는 문제에 보이는 일정한 규칙을 찾아 점화식으로 도출하는 과정이 필수적이다.

문제

입출력

문제 해결 과정

문제를 해결하기 위해서 1에 더하기 경우의 수와 2의 더하기 경우의 수, 3의 더하기 경우의 수를 나눠서 생각했다.

자세히 문제를 본다면 x + x + x + x + x = n 일 경우

• n이 1로 이루어진 경우

  x + x + x + x + 1 = n

  x 는 n - 1

• n이 2로 이루어진 경우

  x + x + x + x + 2 = n

  x 는 n - 2

• n이 3으로 이루어진 경우

  x + x + x + x + 3 = n

  x 는 n - 3

으로 나뉠 수 있다. 그렇다면 d[n] 을 구하려면 d[n-1] 의 경우의 수 + d[n-2] 의 경우의 수 + d[n-3] 의 경우의 수를 합한 것이 될 것이다.

점화식

위의 내용을 점화식으로 나타내면 다음과 같다

d[n] = d[n-1] + d[n-2] + d[n-3] 이라는 점화식이 나오게 된다.

소스 코드(자바)

소스코드를 Top-Down, Bottom-Up 으로 나누어서 작성해보았다.

Top Down

import java.io.*;

public class Main {

    static int[] memo = new int[12];

    public static void main(String[] args) throws IOException {

        BufferedReader input =  new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(input.readLine());

        while(t-- > 0){

            int n = Integer.parseInt(input.readLine());

            output.write(dp(n) + "\n");
        }

        output.flush();

        output.close();

    }

    private static int dp(int n){

        if(memo[n] > 0) return memo[n];

        if(n == 1) return 1;

        else if(n == 2) return 2;

        else if(n == 3) return 4;

        else {

            memo[n] = dp(n-1) + dp(n-2) + dp(n-3);

            return memo[n];
        }
    }
}

Botton-Up

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());

        int[] arr;

        while(t-- > 0){

            int n = Integer.parseInt(br.readLine());

            arr = new int[12];

            arr[0] = 1;

            arr[1] = 2;

            arr[2] = 4;

            for (int i = 3; i < arr.length; i++) {

                arr[i] =  arr[i-3] + arr[i-2] + arr[i-1];

            }
            bw.write(arr[n-1] + "\n");
        }

        bw.flush();

        bw.close();
    }
}