백준 15989 : 1, 2, 3 더하기 4

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

15989번: 1, 2, 3 더하기 4

 

합을 이루고 있는 수의 순서만 다른 것은, 같은 것으로 치는 조건이 붙었습니다.

​

1 = [1] -> 1개

2 = [1+1, 2] -> 2개

3 = [1+1+1, 1+2, 3] -> 3개

4 = [1+1+1+1, 1+1+2, 1+3, 2+2] -> 4개

​

결국 수식의 순서를 바꿔도 중복이 없어야한다는 것인데, 이를 위해 오름차순 조건으로만 수식을 만들 수 있도록 하였습니다.

​

각 수식이 1로 끝나는 것에는 1만 붙일 수 있고,

각 수식이 2로 끝나는 것에는 1, 2만 붙일 수 있고,

각 수식이 3으로 끝나는 것에는 1, 2, 3을 붙일 수 있습니다.

​

각 오름차순 수식에 1 또는 2 또는 3을 붙여 수식을 만들어보겠습니다.

5 = [1+1+1+1+1, 1+1+1+2, 1+2+2, 1+1+3, 2+3] -> 5개 입니다.

​

dp[i][j]는 숫자 i에서 오름차순 수식이 j(1 또는 2 또는 3)로 끝났던 경우의 수입니다.

현재 수 i 에서 1로 끝나는(1을 덧붙이는) 수식의 경우의 수는, i-1에서 만들어졌던 기존의 수식에서 1로 끝났던 수식에만 덧붙일 수 있으므로, 1로만 이루어진 수로 1개 밖에 없습니다. dp[i][1] = 1;

​

현재 수 i 에서 2로 끝나는(2를 덧붙이는) 수식의 경우의 수는, i-2에서 만들어졌던 기존의 수식에서 1, 2로 끝났던 수식에만 덧붙일 수 있으므로,

(i-2에서 1로 끝났던 경우의 수) + (i-1에서 2로 끝났던 경우의 수) = 1 + dp[i-2][2];

​

현재 수 i에서 3으로 끝나는(3을 덧붙이는) 수식의 경우의 수는, i-3에서 만들어졌던 기존의 수식에서 1, 2, 3으로 끝났던 수식에만 덧붙일 수 있으므로,

(i-3에서 1로 끝났던 경우의 수) + (i-3에서 2로 끝났던 경우의 수) + (i-3에서 3으로 끝났던 경우의수) = 1 + dp[i-3][2] + dp[i-3][3];

​

dp[i][1] = 1;

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

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

이므로,

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

dp[i][3] = 1 + dp[i-3][2] + dp[i-3][3]; 입니다.

따라서, 숫자 i에서 만들 수 있는 경우의 수는 1 + dp[i][2] + dp[i][3]입니다.

1, 2, 3에 대해서는 직접 구해주고, 그 이후부터는 점화식을 이용하여 계산해줬습니다.

#include <cstdio>
int t, n, dp[100000][2] = { 0,0,1,0,1,1 };
int main() {
	scanf("%d", &t);
	for (int i = 3; i <= 100000; i++) {
		dp[i][0] = 1 + dp[i-2][0];
		dp[i][1] = 1 + dp[i-3][0] + dp[i-3][1];
	}
	while (t-- && scanf("%d", &n))
		printf("%d\n", 1 + dp[n-1][0] + dp[n-1][1]);
}