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

출처: 

문제

정수 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의 합으로 나타내는 방법의 수를 출력한다.

---

알고리즘

이번 문제는 dp, 점화식 문제입니다.

다음 수가 어떻게 구해지는지 규칙을 찾아서 정수 n을 나타내는 방법의 개수를 찾는 문제로

먼저, 제가 한 방식은 무식한 방법으로 직접 세어보는 것이었습니다.

1부터해서 차례대로 개수가 몇 개인지를 보면

1일 때, 1개 = { 1 }

2일 때, 2개 = { (1, 1), 2 }

3일 때, 4개 = { (1, 1, 1), (1, 2), (2, 1), 3 }

4일 때, 7개 = { (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (1, 3), (3, 1), 4 }

5일 때, 13개 = {...}

접근하는 방법을 몰랐을 때, 검색해서 점화식이라는 것만 알고 규칙을 무식하게 찾아봤습니다..

4부터는 앞의 3개를 합한 값이 방법의 개수가 됩니다.

4는 3과 2와 1의 개수의 합인 7,

5는 4와 3과 2의 개수의 합인 13..

따라서, num[n] = num[n-1] + num[n-2] + num[n-3] (n >= 4)

 

문제를 풀고 검색을 해봤을 때 찾은 방법은

1, 2, 3을 이용해야 하므로 이 3개를 기준으로 생각하는 방법이었습니다.

 

1일 때는 1개

2일 때는 1+1이므로 1의 개수인 1개

            2 로 1개 해서 총 2개

            

3일 때는 1+2이므로 2의 개수인 2개

            2+1이므로 1의 개수인 1개

            3으로 1개 해서 총 4개

 

4일 때는 1+3이므로 3의 개수인 4개

            2+2이므로 2의 개수인 2개

            3+1이므로 1의 개수인 1개

            해서 총 7개

 

5일 때는 1+4이므로 4의 개수인 7개

            2+3이므로 3의 개수인 4개

            3+2이므로 2의 개수인 2개

            해서 총 13개

 

이런 식으로 규칙을 찾아낸 것을 알았습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt(br.readLine());
		int[] num = new int[11];
		num[1] = 1;
		num[2] = 2;
		num[3] = 4;
		
		for(int i = 0; i < t; i++) {
			int n = Integer.parseInt(br.readLine());
            		for(int j = 4; j <= n; j++) {
				num[j] = num[j-1] + num[j-2] + num[j-3];
			}
			sb.append(num[n]).append('\n');
		}
		System.out.println(sb);
	}
}

---

몇 번 풀어봤지만 dp, 점화식 문제는 어려운 것 같습니다.

'딱 봐도 점화식이다', '규칙을 찾아야 하겠구나' 하는 생각이 들 정도로 풀어봐야겠습니다.

이 글의 알고리즘이나 코드에서 지적할만한 부분은 댓글에 남겨주시면 저에게 많은 힘이 됩니다!