[BOJ] 1309번: 동물원

1309번: 동물원

지극히 개인적인 생각입니다. 제대로된 풀이는 다른 블로그 보시길 바랄게요 죄송합니다!

문제가 규칙성을 찾을 수 있을 것 같아서 야매로 찾다가 3 7 17 41이 나오길래 

int n, ret = 3;
scanf("%d", &n);
int plus = 4, add = 6;
for (int i = 1; i < n; ++i) {
    ret += plus, ret %= R;
    plus += add, add += 8;
}

했지만 당연히 틀렸다.

그래서 "스티커"문제의 경험을 되살려서 대각선으로만 놓을 수 있다는 것에 착안을 했다.

dp[0][i] = dp[1][i - 1] + dp[0][i - 2] + dp[1][i - 2]

dp[1][i] = dp[0][i - 1] + dp[0][i - 2] + dp[1][i - 2]

이러고 나서 dp[0][n] + dp[1][n]을 출력하려고 했는데 생각해보니 dp[0][i - 2] + dp[1][i - 2]이 중복되길래 dp 배열을 1차원으로 바꿔서

dp[i] = dp[i - 1] * 2 + dp[i - 2]로 했더니 맞았다.

코드

#include <cstdio>

const int R = 9901;
int dp[100001];

int main()
{
    int n;
    scanf("%d", &n);
    dp[0] = 1, dp[1] = 3;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] * 2 + dp[i - 2];
        dp[i] %= R;
    }
    printf("%d", dp[n]);
    return 0;
}