https://www.acmicpc.net/problem/15991
15991번: 1, 2, 3 더하기 6
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
정수 N을 만드는 방법의 수를 구하는 문제인데 이 문제는 식이 대칭을 이루어야 합니다.
예를들어 N = 4일 때 1+1+1+1, 1+2+1, 2+2 이런 식은 가능하지만
1+1+2, 2+1+1, 1+3, 3+1 이런 식은 대칭을 이루지 않아 안된다는 점입니다.
대칭이라는 점을 이용하여,
N - 2를 이루는 식의 양 옆에 1씩 더하는 경우,
N - 4를 이루는 식의 양 옆에 2씩 더하는 경우,
N - 6을 이루는 식의 양 옆에 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]; void init() { dp[0] = 1; dp[1] = 1; dp[2] = 2; dp[3] = 2; dp[4] = 3; dp[5] = 3; for (int i = 6; i <= 100000; i++) { dp[i] = ((dp[i - 2] + dp[i - 4]) % MOD + dp[i - 6]) % 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] << '\n'; } return 0; } | cs |
'algorithm > dp' 카테고리의 다른 글
| boj 15993 1, 2, 3 더하기 8 (0) | 2021.01.22 |
|---|---|
| boj 15992 1, 2, 3 더하기 7 (0) | 2021.01.22 |
| boj 15990 1, 2, 3 더하기 5 (0) | 2021.01.22 |
| boj 15989 1, 2, 3 더하기 4 (0) | 2021.01.22 |
| boj 15988 1, 2, 3 더하기 3 (0) | 2021.01.22 |