백준 9095번, 1, 2, 3 더하기(with.Java)

백준 9095번, 1, 2, 3 더하기(with.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의 합으로 나타내는 방법의 수를 출력한다.

문제 풀이

import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine());

		for (int t = 0; t < T; t++) {
			int n = Integer.parseInt(br.readLine());
			int[] dp = new int[11];

			dp[1] = 1;
			dp[2] = 2;
			dp[3] = 4;

			for (int i = 4; i <= n; i++) {
				dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
			}

			bw.write(dp[n] + "\n");
		}
		bw.flush();
	}
}

풀이 설명

이 코드는 동적 프로그래밍을 활용하여 정수 num을 1, 2, 3의 합으로 나타내는 방법의 수를 계산하는 프로그램입니다.

수학적으로 이해하기 쉽게 예제를 들어 설명해 보겠습니다.

• 숫자 i를 만드는 모든 경우는
  • (i-1을 만들고 1을 더하는 경우)
  • (i-2를 만들고 2를 더하는 경우)
  • (i-3을 만들고 3을 더하는 경우)
• 이 세 가지 방법이 서로 겹치지 않으므로, 총 경우의 수는
  [ dp[i] = dp[i-1] + dp[i-2] + dp[i-3] ] 로 정의할 수 있습니다.

이제 (i-1) + (i-2) + (i-3) = i라는 의미가 아니라, i를 만들 수 있는 모든 경우를 점화식으로 표현한 것이라는 점이 이해되었을 것입니다.