[백준/Baekjoon] 1309 동물원 C++ :: Dynamic Programming

https://www.acmicpc.net/problem/1309

1309번: 동물원

---

1. Logic

이 문제의 부분문제는 총 3가지로 나눌 수 있다. 

1. 사자를 배치하지 않는 경우(항상)

2. 사자를 오른쪽에 배치하는 경우(이전에 사자를 왼쪽에 배치했을 때)

3. 사자를 왼쪽에 놓는경우 (이전에 사자를 오른쪽에 배치했을때)

 

이렇게 3가지 경우를 끊어서 해결해주면 된다.

아래 코드를 보면 이해가 될 것이다.

---

2. Code

#include <iostream>
#include <cstring>
using namespace std;

int n;
int dp[100001][3];

int solve(int idx, int prev) {
    if(idx == n) return 1;
    int &ret = dp[idx][prev];
    
    if(ret != -1) return ret;
    
    ret = 0;
    
    
    if(prev == 0) {
        ret += solve(idx+1, 0);
        ret += solve(idx+1, 1);
        ret += solve(idx+1, 2);
    }
    else if(prev == 1) {
        ret += solve(idx+1, 0);
        ret += solve(idx+1, 2);   
    }
    else if(prev == 2) {
        ret += solve(idx+1, 0);
        ret += solve(idx+1, 1);
    }
    
    
    return ret %= 9901;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
    cin >> n;
    
    cout << solve(0, 0);
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐