[백준/9095/Java] 1, 2, 3 더하기

 

문제:

www.acmicpc.net/problem/9095

9095번: 1, 2, 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의 합으로 나타내는 방법의 수를 구해야 합니다.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어집니다.

n은 양수이며 11보다 작습니다.

 

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력합니다.

 

 

풀이

쓸 수 있는 숫자는 1, 2, 3으로 세 개입니다.

그러면 규칙을 찾아보기 위해서 합이 1부터 되는 경우의 수부터 세어보도록 하겠습니다.

합이 N이 되는 방법의 수는 D[N]로 표현하도록 하겠습니다.

그러면 D[1] = 1, D[2] = 2, D[3] = 4, D[4] = 7, D[5] = 13입니다.

N	1	2	3	4	5
경우의 수	1	1 + 1 2	1 + 1 + 1 1 + 2 2 + 1 3	1 + 1 + 1+ 1 1 + 1 + 2 1 + 2 + 1 2 + 1 + 1 2 + 2 1 + 3 3 + 1	1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 2 + 1 + 1 2 + 1 + 1 + 1 1 + 2 + 2 2 + 2 + 1 2 + 1 + 2 1 + 1 + 3 1 + 3 + 1 3 + 1 + 1 2 + 3 3 + 2
방법의 수 (D[N])	1	2	4	7	13

 

규칙을 찾기 위해서 경우의 수에서 순서를 바꿔보도록 하겠습니다.

D[4], D[5]에서 기존에 존재하던 경우의 수에서 추가적으로 더하는 숫자를 핑크 배경색으로 표시하였습니다.

N	1	2	3	4	5
경우의 수	1	1 + 1 2	1 + 1 + 1 1 + 2 2 + 1 3	D[1] 1 + 3 D[2] 1 + 1 + 2 2 + 2 D[3] 1 + 1 + 1 + 1 1 + 2 + 1 2 + 1 + 1 3 + 1	D[2] 1 + 1 + 3 2 + 3 D[3] 1 + 1 + 1 + 2 1 + 2 + 2 2 + 1 + 2 3 + 2 D[4] 1 + 1 + 1+ 1 + 1 1 + 1 + 2 + 1 1 + 2 + 1 + 1 2 + 1 + 1 + 1 2 + 2 + 1 1 + 3 + 1 3 + 1 + 1
방법의 수 (D[N])	1	2	4	7	13

 

 

보시면 4가 되는 경우의 수 D[4]를 구하려면

D[1] 경우의 수에서 +3만 더하면 4가 됩니다.

  1 + 3

D[2] 경우의 수에서 +2만 더하면 4가 됩니다.

  1 + 1 + 2
  2 + 2

D[3] 경우의 수에서 +1만 더하면 4가 됩니다.

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

따라서, D[4] = D[1] + D[2] + D[3]이 된다는 것을 알 수 있습니다.

 

D[5]를 보시면 D[2], D[3], D[4] 경우의 수가 모두 포함되므로

D[N] = D[N-1] + D[N-2] + D[N-3]이 된다는 것을 알 수 있습니다.

 

 

소스

n이 되는 경우의 수를 구하므로 D[N]을 구하면 됩니다.

단, D[1], D[2], D[3]은 D[N-3]이 존재할 수 없는 경우이므로 

D[1] = 1, D[2] = 2, D[3] = 4로 초기값을 설정해줍니다.

D[3]은 N-3이 D[0]인데 여기에 1을 설정해도 동일하게 4로 나옵니다. (0+3은 3이므로 경우의 수가 1입니다.)

D[3] 초기값은 편하신 방법으로 설정해주시면 됩니다.

 

import java.util.Scanner;

public class Main
{
	static int T;
	static int N;
	static int D[] = new int[11];

	public static void main(String[] args) throws Exception
	{
		Scanner sc = new Scanner(System.in);
	
		T = sc.nextInt();
		
		for (int test_case = 1; test_case <= T; test_case++)
		{
			N = sc.nextInt();

			// 조합
			// 1 = 1
			// 2 = 2
			// 3 = 4
			// 4 = 7
			// 5 = 13
			D[0] = 1;
			D[1] = 1;
			D[2] = 2;
			for (int i = 3; i <= N; i++)
			{
				D[i] = D[i-1] + D[i-2] + D[i-3];
			}
			
			System.out.println(D[N]);
		}
	}
}