[BOJ 길라잡이/Java] 14일차 #9095 1, 2, 3 더하기

알고리즘 분류

- 다이나믹 프로그래밍

 

주어진 정수 n(양수, 11보다 작음)을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제다.

 

공책에 쭉쭉 경우의 수를 적다가 규칙을 발견했다.

cases[n] = cases[n-1] + cases[n-2] + cases[n-3]

이렇게 n의 방법의 수는 n-1, n-2, n-3의 방법의 수를 모두 합친 것과 같다는 것이었다.

써내려가다보니

cases[1] = 1

cases[2] = 2

cases[3] = 4

cases[4] = 7

cases[5] = 13

cases[6] = 24

cases[7] = 44

cases[8] = 81

cases[9] = 149

cases[10] = 274

이런 식으로 값이 나왔다.

 

작성한 코드는 다음과 같다.

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp(n)).append("\n");
        }

        System.out.println(sb);
                
    }

    private static int dp(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else if (n == 3) {
            return 4;
        } else {
            return dp(n-1) + dp(n-2) + dp(n-3);
        }
    }
}

 

예전에 풀었던 방법을 보니

어차피 n이 11보다 작다고 문제에 주어져 있으므로

dp[4]부터 dp[10]까지 값을 모두 구한 뒤

n에 해당하는 값만 출력해도 됐다.

 

이게 이전에 작성했던 코드다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] dp = new int[11];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        dp[1] = 1; // 1
        dp[2] = 2; // 1+1, 2
        dp[3] = 4; // 1+1+1, 1+2, 2+1, 3

        for (int i = 4; i < 11; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n]);
        }
    }
}