https://www.acmicpc.net/problem/15993
15993번: 1, 2, 3 더하기 8
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.
www.acmicpc.net
1, 2, 3 더하기 8번째 문제입니다.
이 문제는 7번째 문제와 비슷한 유형이라고 볼 수 있습니다.
7번째 문제에서는 M개의 수를 사용하여 N을 만드는 방법인데 이를 홀수, 짝수로 나누면 되는 문제입니다.
dp[N][0] → N을 만드는 방법 중 홀수개를 사용하는 경우
dp[N][1] → N을 만드는 방법 중 짝수개를 사용하는 경우
7번째 문제에서 dp[N]는 dp[N - 1]에서 +1, dp[N - 2]에서 +2, dp[N - 3]에서 +3을 한 것이라고 했었습니다.
즉, 갯수가 1개가 늘어난다는 말은 홀수는 짝수가 되고, 짝수는 홀수가 된다는 말입니다.
따라서 홀수의 갯수는 N - 1, N - 2, N - 3번째의 수를 짝수개를 사용하여 나타내는 방법의 수를 더한 값이고,
짝수의 갯수는 N - 1, N - 2, N - 3번째의 수를 홀수개를 사용하여 나타내는 방법의 수를 더한 값이 되겠습니다.
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 | #include <iostream> #define MOD 1000000009 using namespace std; int dp[100001][2]; void init() { dp[1][0] = 1; dp[2][0] = 1; dp[2][1] = 1; dp[3][0] = 2; dp[3][1] = 2; for (int i = 4; i <= 100000; i++) { dp[i][0] = ((dp[i - 1][1] + dp[i - 2][1]) % MOD + dp[i - 3][1]) % MOD; dp[i][1] = ((dp[i - 1][0] + dp[i - 2][0]) % MOD + dp[i - 3][0]) % MOD; } } int main() { cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false); init(); int tc, N; cin >> tc; while (tc--) { cin >> N; cout << dp[N][0] << ' ' << dp[N][1] << '\n'; } return 0; } | cs |
'algorithm > dp' 카테고리의 다른 글
| boj 12852 1로 만들기 2 (0) | 2021.01.22 |
|---|---|
| boj 16195 1, 2, 3 더하기 9 (0) | 2021.01.22 |
| boj 15992 1, 2, 3 더하기 7 (0) | 2021.01.22 |
| boj 15991 1, 2, 3 더하기 6 (0) | 2021.01.22 |
| boj 15990 1, 2, 3 더하기 5 (0) | 2021.01.22 |