[백준] 9095번: 1, 2, 3 더하기 - JAVA

🔗 문제 링크

BOJ 9095번: 1, 2, 3 더하기

9095번: 1, 2, 3 더하기

 

📝 풀이 과정

문제를 보고 1부터 차례대로 구할 수 있는 모든 경우를 쓰기 시작하였다.

(1)
1
---
(2)
1 + 1
2
---
(3)
1 + 1 + 1
2 + 1
1 + 2
3
---
(4)
1 + 1 + 1 + 1
2 + 1 + 1
1 + 2 + 1
1 + 1 + 2
2 + 2
3 + 1
1 + 3
---
(5)
1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1
1 + 2 + 1 + 1
1 + 1 + 2 + 1
1 + 1 + 1 + 2
2 + 2 + 1
...

쓰다보면서 일정한 패턴이 반복된다고 느끼게 되었다. 앞의 계산들이 반복되고 뒤에 하나만 붙이면 계산 결과가 나온다는 것이다.

 

 

(4)
1 + 1 + 1 + 1
2 + 1 + 1
1 + 2 + 1
3 + 1         ... (1)

1 + 1 + 2
2 + 2         ... (2)

1 + 3         ... (3)

4의 경우의 수를 구할 때, 위와 같이 3개로 분리할 수 있다. (1)은 정수 3을 구할 수 있는 경우에서 + 1을 한 결과이고, (2)는 정수 2를 구할 수 있는 경우에서 + 2를 한 결과라는 것이다. 마찬가지로 (3)은 정수 1을 구하는 경우에서 + 3을 한 결과이다.

 

이와 같은 계산을 통해 $dp[n] = dp[n-1]+dp[n-2]+dp[n-3] (n>=3)$이라는 점화식이 나오게 된다.

입력 값에 따라 배열이 변하지 않으므로 미리 반복문을 통해 n=10일 때까지 구해둔 뒤, 입력 값에 따른 memo[n]값을 출력해준다.

 

💻 코드

import java.util.Scanner;

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

        int[] memo = new int[11];
        memo[1] = 1;
        memo[2] = 2;
        memo[3] = 4;
        for (int i = 4; i <= 10; i++)
            memo[i] = memo[i - 1] + memo[i - 2] + memo[i - 3];

        for (int tc = 1; tc <= T; tc++) {
            int n = sc.nextInt();
            System.out.println(memo[n]);
        }
    }
}

 

📊 제출 결과