1309 동물원

BOJ::1309 동물원

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

dp문제.

n번째 우리에 대해

왼쪽에 사자를 놓는 경우, 오른쪽에 사자를 놓는 경우, 둘 다 놓지 않는경우 3가지로 나눠서 풀었다.

점화식 :

d[n][0] = d[n-1][1]+d[n-1][2];

d[n][1] = d[n-1][0]+d[n-1][2];

d[n][2] = d[n-1][0]+d[n-1][1]+d[n-1][2];

JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
class Main{
    
    static int n;
    static int d[][]=new int[100001][3];
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(br.readLine());
        
        d[1][0]=1;
        d[1][1]=1;
        d[1][2]=1;
        
        for(int i = 2 ; i <= n ;i++){
            d[i][0]=(d[i-1][1]+d[i-1][2])%9901;
            d[i][1]=(d[i-1][0]+d[i-1][2])%9901;
            d[i][2]=(d[i-1][1]+d[i-1][2]+d[i-1][0])%9901;
        }
        
        System.out.println((d[n][0]+d[n][1]+d[n][2])%9901);
        
    }
}

C++

#include <iostream>
using namespace std;
 
int n;
int d[100001][3];
 
int main() {
    cin >> n;
    
    d[1][0] = 1;
    d[1][1] = 1;
    d[1][2] = 1;
 
    for (int i = 2; i <= n; i++) {
        d[i][0] = (d[i - 1][1] + d[i - 1][2])%9901;
        d[i][1] = (d[i - 1][0] + d[i - 1][2])%9901;
        d[i][2] = (d[i - 1][0] + d[i - 1][1] + d[i - 1][2])%9901;
    }
 
    cout << (d[n][0] + d[n][1] + d[n][2]) % 9901 << endl;
}