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

• 문제 링크

9095번: 1, 2, 3 더하기

 

• 풀이 과정

규칙성을 발견하기 위해 n이 1 ~ 4 일 때 1, 2, 3 의 합으로 나타내는 경우의 수을 표현하면 아래와 같다.

n = 1	(1)
n = 2	(1 + 1) (2)
n = 3	(1 + 1 + 1) (1 + 2) (2 + 1) (3)
n = 4	(1 + 1 + 1 + 1) (1 + 1 + 2) (1 + 2 + 1) (2 + 1 + 1) (2 + 2) (1 + 3) (3 + 1)

위와 같이 n = 4 일 때 모든 경우의 수는 1 ~ 3 의 모든 경우의 수를 포함한다.

이에 대한 점화식을 dp 배열을 활용한 코드에 적용하면 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 이 성립한다.

 

문제에 제시된 조건에 따라 dp 배열의 크기를 11로 설정하고

1 ~ 3 의 경우의 수는 이미 알고 있으므로 각각의 인덱스에 해당 값으로 초기화한 후 

for 문 안에 점화식을 대입하여 정답을 반환한다.

 

• 풀이 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		for (int i = 0; i < t; i++)
			bw.write(getSum(Integer.parseInt(br.readLine())) + "\n");

		bw.flush();
	}

	private static int getSum(int n) {
		int[] dp = new int[11];

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

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

		return dp[n];
	}

}