BOJ 15993번 1, 2, 3 더하기 8

BOJ : https://www.acmicpc.net/problem/15993

github : https://github.com/junho0956/Algorithm/blob/master/15993/15993/%EC%86%8C%EC%8A%A4.cpp

 

오랫동안 고민했는데 못풀었습니다.

딱히 규칙이 눈에 보이지 않았고 재귀로 짜볼려니 구현하다가 막히고 ㅠ

 

(emoney96 친구가 문제를 보자말자 해결해줬습니다. 존경하는 그저 갓.. )

 

점화식 dp[num] 은 홀수기준 짝수dp의 -1, -2, -3 을 모두 더한 값, 짝수기준 홀수dp의 -1,-2,-3 을 모두 더한 값 입니다.

왜 저는 이런 규칙이 안보이는건지 씁쓸합니다.. 다시 한번 갓 emoney96..

이렇게 해서 1,2,3 더하기 시리즈 해결했네요!

 

#include <iostream>
typedef long long ll;
using namespace std;
 
ll odd[100001];
ll even[100001];
const int mod = 1e9 + 9;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    odd[1] = 1, odd[2] = 1, odd[3] = 2;
    even[1] = 0, even[2] = 1, even[3] = 2;
 
    for (int i = 4; i <= 100000; i++)
        odd[i] = (even[i - 1] + even[i - 2] + even[i - 3])%mod, even[i] = (odd[i - 1] + odd[i - 2] + odd[i - 3])%mod;
 
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << odd[n] << " " << even[n] << "\n";
    }
 
    return 0;
}