[백준/JAVA] BOJ 9095 - 1, 2, 3 더하기

👀 문제

9095번: 1, 2, 3 더하기 ✨ 실버 3

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

🔑 키포인트

다이나믹 프로그래밍

👩🏻‍💻 점화식

죄다 계산해서 써 보니 점화식이 나왔다.
dp는 너무 어려워... 노가다가 답이 아닐 텐데 말이다... 🥹

1 -> 1
2 -> 2
3 -> 4
4 -> 7
5 -> 13
6 -> 24
7 -> 44
.
.
.

dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

✍️ 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();

        int dp[] = new int[10];

        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 4;

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

        for (int i = 0; i < t; i++) {
            int num = s.nextInt();
            System.out.println(dp[num-1]);
        }

        s.close();
    }
}

이제 알고리즘 풀이 언어를 다시 자바로 바꿔보려고 한다.
적응 기간이라 생각하고 쉬운 문제부터 다시 차근히 풀어나가야지. 🙃