(21.12.31) (Baekjoon 9095) 1,2,3 더하기(Java)

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

입력한 숫자를 1,2,3으로 표현할 수 있는 경우의 수를 모두 구하는 문제이다.

ex)

4를 구하고자 할때

1+1+1+1

1+1+2

1+2+1

1+3

2+1+1

2+2

3+1

으로 하여 총 7가지의 경우가 나온다.

구해야 할 경우의 수를 모아놓는 배열을 dp[] 라고 칭했을 때

dp[1] = 1, dp[2] = 2, dp[3] = 4가 나온다는 걸 기본 전제로 깔고 가자.

4부터는 본격적으로 어떻게 경우를 나눠야 하는지를 골라야 하는데,

위의 경우를 잘 보면

1 + (1+1+1 // 1+2 // 2+1 // 3) 이 dp[4]가 되는 경우가 되고

2 + (1+1 // 2) 도 dp[4]가 되는 경우가 되고

3 + 1도 dp[4]가 되는 경우가 된다.

즉, dp[4] = dp[3] + dp[2] + dp[1]이 되는 것을 알 수 있다.

 

다른 예시도 들어보자.

5를 구하고자 할 때

1+1+1+1+1

1+1+1+2

1+1+2+1

1+1+3

1+2+1+1

1+2+2

1+3+1

 

2+1+1+1

2+1+2

2+2+1

2+3

 

3+1+1

3+2

 

여기서도 dp[5]는

1+ dp[4]의 경우가 있고

2 + dp[3]이 있고

3 + dp[2]가 있다.

 

결국 이를 점화식으로 표현하면 

dp[i] = dp[i-1]+dp[i-2]+dp[i-3];

이 나오게 된다.

//1,2,3의 경우엔 기본적으로 값을 선언해놓는다.
		ar[1] = 1;
		ar[2] = 2;
		ar[3] = 4;
		for (int i = 4; i <= 10; i++) {
			ar[i] = ar[i-1] + ar[i-2] + ar[i-3];
		}

 

이렇게 하면 답이 나오는 기본적인 DP 문제였다.

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

public class Main {
	static int T,N;
	static int[] ar;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		ar = new int[11];
		ar[1] = 1;
		ar[2] = 2;
		ar[3] = 4;
		for (int i = 4; i <= 10; i++) {
			ar[i] = ar[i-1] + ar[i-2] + ar[i-3];
		}
		for (int i = 0; i < N; i++) {
			int n = Integer.parseInt(br.readLine());
			System.out.println(ar[n]);
		}

	}

}