https://www.acmicpc.net/problem/15992
15992번: 1, 2, 3 더하기 7
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다.
www.acmicpc.net
1, 2, 3 더하기 7번째 문제입니다.
이 문제는 정수 N을 1, 2, 3으로 나타내는 방법에서 M개의 수를 사용한 방법의 수를 출력하는 문제입니다.
dp[N][M] = N을 M개의 수로 나타내는 방법의 수
지금까지 1, 2, 3 더하기 문제는 대부분 N - 1에서 +1, N - 2에서 +2, N - 3에서 +3을 한 방법의 수를 구하는 문제였습니다. 즉, 하나의 수를 더했다는 말이 됩니다.
그러므로 dp[N][M]는
dp[N - 1][M - 1] (N - 1을 M - 1개의 수로 나타내는 방법의 수)와
dp[N - 2][M - 1] (N - 2을 M - 1개의 수로 나타내는 방법의 수)와
dp[N - 3][M - 1] (N - 3을 M - 1개의 수로 나타내는 방법의 수)를
더해주는 방법의 수가 되겠습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include <iostream> #define MOD 1000000009 using namespace std; int dp[1001][1001]; void init() { dp[1][1] = 1; dp[2][1] = 1; dp[2][2] = 1; dp[3][1] = 1; dp[3][2] = 2; dp[3][3] = 1; for (int i = 4; i <= 1000; i++) { for (int j = 1; j <= i; j++) { dp[i][j] = ((dp[i - 1][j - 1] + dp[i - 2][j - 1]) % MOD + dp[i - 3][j - 1]) % MOD; } } } int main() { cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false); init(); int tc, N, M; cin >> tc; while (tc--) { cin >> N >> M; cout << dp[N][M] << '\n'; } return 0; } | cs |
'algorithm > dp' 카테고리의 다른 글
| boj 16195 1, 2, 3 더하기 9 (0) | 2021.01.22 |
|---|---|
| boj 15993 1, 2, 3 더하기 8 (0) | 2021.01.22 |
| boj 15991 1, 2, 3 더하기 6 (0) | 2021.01.22 |
| boj 15990 1, 2, 3 더하기 5 (0) | 2021.01.22 |
| boj 15989 1, 2, 3 더하기 4 (0) | 2021.01.22 |