[백준][C++] 15989: 1, 2, 3 더하기 4

문제 링크: https://www.acmicpc.net/problem/15989

 

다이나믹 프로그래밍 문제입니다. bottom-up 방식으로 풀어봤습니다.

일단 문제에 없는 조건 '오름차순으로만 더할 수 있다'를 추가해봅니다. 왜냐면 그렇게 해야 중복으로 세는 경우를 뺄 수 있거든요.

그리고 dp 식을 적어보면 아래와 같습니다.

\[ dp[i][j] = \text{정수 i를 만들 때 마지막으로 더한 수가 j인 경우의 수} \]

 

더할 수 있는 1, 2, 3이니까 경우의 수를 아래처럼 나눌 수 있습니다.

• 마지막에 더한 수가 1인 경우: 바로 앞에 더한 수는 1밖에 나올 수 없습니다
• 마지막에 더한 수가 2인 경우: 바로 앞에 더한 수가 1, 2가 나올 수 있습니다
• 마지막에 더한 수가 3인 경우: 바로 앞에 더한 수가 1, 2, 3이 나올 수 있습니다

이걸 식으로 정리하면

\begin{align}
dp[i][1] &= 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]
\end{align}

인 걸 알 수 있습니다.

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


long long dp[10001][3];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;

	dp[0][0] = 1;
	for (int i = 1; i <= 10000; ++i) {
		dp[i][0] = dp[i - 1][0];
		if (i > 1)
			dp[i][1] = dp[i - 2][0] + dp[i - 2][1];
		if (i > 2)
			dp[i][2] = dp[i - 3][0] + dp[i - 3][1] + dp[i - 3][2];
	}
	
	while (n--) {
		int in;
		cin >> in;
		cout << accumulate(dp[in], dp[in] + 3, 0LL) << '\n';
	}


	return 0;
}

bottom-up 방식으로 구현한 코드입니다.

위에 쓴 식과 다른 점이 dp[i][j]에서 j 부분이 0, 1, 2인데 그냥 다음부터는 [4]로 선언해서 [1, 2, 3] 이런식으로 써야겠습니다. 헷갈리네요. 메모리 좀 더 쓴다고 죽는 것도 아니니까요