[백준(baekjoon) 9095] 1, 2, 3 더하기

문제

백준 9095

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

• 예시 n = 4;
  1+1+1+1 / 1+1+2 / 1+2+1 / 2+1+1 / 2+2 / 1+3 / 3+1
• input
  
  • 첫째줄 : T(테스트 개수)
  • 그 다음 줄 부터 : n(11보다 작은 자연수, T번 반복됨)

해결

우리가 찾고자 하는 수는 1, 2, 3의 조합이다. 

즉, 쉽게 생각해 1, 2, 3으로 각각 시작하는 경우의 수를 모두 찾아보면 답이 나온다.

예를 들어 n = 6라고 할 때, 1, 2, 3 을 기준으로 생각해 본다면,
6 = 1 + 5, 6 = 2 + 4, 6 = 3 + 3로 나타낼 수 있다.
즉 n = 6의 경우, [n = 5의 조합 수] + [n = 4의 조합 수] + [n = 3의 조합 수]가 된다.

하지만 1, 2, 3 은 자기 자신만으로 나타 낼 수 있고, 3개가 아닌 n개의 케이스로 나뉜다.는 것을 유의하면 된다.

알고리즘

DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

공통적인 것

• answer에 값들을 저장한다는 것
  
  • n < 11이고 수가 작아 아예 11로 크기를 정의하고 접근하기 쉽게 index = 1부터 시작하였다.

1. Top-Down 방식

1.import java.util.*;
2.
3.public class Main {
4.    static int[] answer = new int[11];
5.    public static void main (String[] args) {
6.        Scanner sc = new Scanner(System.in);
7.        int T = sc.nextInt();
8.
9.        goTo(10);
10.
11.        for (int i = 0; i < T; i++) {
12.            int n = sc.nextInt();
13.            System.out.println(answer[n]);
14.        }
15.    }
16.
17.    public static int goTo (int n) {
18.        if (n <= 3) answer[n] = 1;
19.        for (int i = 1; i <= 3 && i < n; i++) {
20.            answer[n] += answer[n - i] == 0 ? goTo(n - i) : answer[n - i];
21.        }
22.        return answer[n];
23.    }
24.}

2. Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    static int[] answer = new int[11];
5.    public static void main (String[] args) {
6.        Scanner sc = new Scanner(System.in);
7.        int T = sc.nextInt();
8.
9.        for (int i = 1; i <= 10; i++) {
10.            if (i < 4) answer[i] = 1;
11.            for (int j = 1; j <= 3 && j < i; j++) {
12.                answer[i] += answer[i - j];
13.            }
14.        }
15.
16.        for (int i = 0; i < T; i++) {
17.            int n = sc.nextInt();
18.            System.out.println(answer[n]);
19.        }
20.    }
21.}

결과

1. Bottom-Up 방식
2. Top-Down 방식