1, 2, 3 더하기

📍 문제 설명

 

💡 접근

1.n을 넘지 않는 모든 합의 경우의 수를 모두 구해보면 된다.

2.보텀업 방식으로 1,2,3을 만들 수 있는 가짓수를 구해놓고 4부터 dp 테이블에 가짓수를 구해나가면 된다.

 

👩‍💻 코드

1.브루트포스

import java.util.*;

public class Main {
    static int n, m, answer, cnt, min;
    static int[][] board,clone;
    static boolean[] arr;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        int t = kb.nextInt();
        for(int i = 0; i < t; i++) {
            n = kb.nextInt();
            answer = 0;
            T.solution(0);
            System.out.println(answer);
        }
    }

    private void solution(int s) {
        if(s > n) return;
        if(s == n) answer++;
        else {
            for(int i = 1; i <= 3; i++) {
                solution(s+i);
            }
        }
    }
}

 

2.DP

import java.util.*;

public class Main {
    static int n, m, answer, cnt, min;
    static int[][] board,clone;
    static boolean[] arr;
    static boolean[][] visited;
    static int[] breakdown;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        int t = kb.nextInt();
        for(int i = 0; i < t; i++) {
            n = kb.nextInt();
            int[] dp = new int[n+1];
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;
            for(int j = 4; j <= n; j++) {
                dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
            }
            System.out.println(dp[n]);
        }
    }

    private void solution() {
    }
}