문제
https://www.acmicpc.net/problem/15992
문제 요약
정수 n을 m개의 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
코드
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
int t;
int dp[1010][1010];
ll dfs(int n, int m) {
// 음수일 경우 0
if (n <= 0 || m <= 0) return 0;
// 이미 메모이제이션 테이블에 값이 있는 경우
if (dp[n][m] != -1) return dp[n][m];
return dp[n][m] = (dfs(n - 1, m - 1) + dfs(n - 2, m - 1) + dfs(n - 3, m - 1)) % 1000000009;
}
int main() {
cin >> t;
// 초기 설정
memset(dp, -1, sizeof(dp));
dp[1][1] = 1;
dp[2][1] = 1;
dp[2][2] = 1;
dp[3][1] = 1;
dp[3][2] = 2;
dp[3][3] = 1;
while (t--) {
ll n, m;
cin >> n >> m;
cout << dfs(n, m) << "\n";
}
return 0;
}
코드 설명
1. 메모이제이션 테이블 dp를 정의한다. dp[i][j]는 정수 i를 j개의 1, 2, 3의 합으로 나타낼 수 있는 방법 수이다.
2. n이 1, 2, 3일 경우에 대한 dp 초기값을 설정한다. (아직 dp 값을 모르는 경우 -1)
3. dfs(n, m)을 통해 정수 n을 m개의 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 완전탐색(백트래킹)한다.
4. 탐색을 진행하면서, n과 m이 음수일 경우 방법이 없으므로 0을 반환하고, dp에 이미 값이 구해져 있다면 재귀를 진행하지 않고 즉시 값을 반환한다.
'Algorithm Problems > 다이나믹 프로그래밍' 카테고리의 다른 글
[백준/C++] 9252번: LCS 2 (0) | 2024.07.09 |
---|---|
[백준/C++] 17626번: Four Squares (0) | 2024.07.08 |
[백준/C++] 10844번: 쉬운 계단 수 (0) | 2024.03.24 |
[백준/C++] 1912번: 연속합 (1) | 2024.03.23 |
[백준/C++] 2579번: 계단 오르기 (0) | 2024.03.22 |