백준 9095 자바 - 1, 2, 3 더하기

문제

---

 

 

 

문제해결

---

- 정수 1을 1, 2, 3의 합으로 나타내는 방법은 

1

총 1개

- 정수 2를 1, 2, 3의 합으로 나타내는 방법은 

1 + 1

2

총 2개

- 정수 3을 1, 2, 3의 합으로 나타내는 방법은 

1 + 1 + 1

1 + 2

2 + 1

3

총 4개

 

- 그렇다면 정수 4를 1, 2, 3의 합으로 나타내는 방법은 

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

1 + 3

(4)

2 + 1 + 1

2 + 2

(2)

3 + 1

(1)

이렇게 4 + 2 + 1 = 7가지다, 잘 보면

1 + 우측에는 3을 나타내는 경우의 수(4)

2 + 우측에는 2를 나타내는 경우의 수(2)

3 + 우측에는 1을 나타내는 경우의 수(1)

즉 3의 경우의수 + 2의 경우의 수 + 1의 경우의 수인것을 볼수 있다

 

- 여기서 정수 5를 1, 2, 3의 합으로 나타내는 방법은

1 + 1 + 1 + 1 + 1

1 + 1 + 1 + 2

1 + 1 + 2 + 1

1 + 1 + 3

1 + 2 + 1 + 1

1 + 2 + 2

1 + 3 + 1

(7)

2 + 1 + 1 + 1

2 + 1 + 2

2 + 2 + 1

2 + 3

(4)

3 + 1 + 1

3 + 2

(2)

이렇게 7 + 4 + 2가 된다

이번에도 맨 왼쪽의 숫자를 기준으로 1, 2 ,3을 나눠서 보면 4의 경우의수 + 3의 경우의 수 + 1의 경우의 수이다

그러므로 점화식인 dp 배열을 아래와 같이 정의할 수 있다

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

- 이번 문제에서는 n이 11보다 작으니 10까지의 dp 배열을 먼저 구하고 결과를 출력한다

import java.util.Scanner;
//dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
public class B9095 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int[] dp = new int[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        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 = sc.nextInt();
            System.out.println(dp[n]);
        }
    }
}