[JAVA] 백준 1309번- 동물원

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

1309번: 동물원

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
		
        long[] dp = new long[n+1];

        dp[0] = 1;
        dp[1] = 3;

        for(int i=2; i<=n; i++){
            dp[i] =( 2*dp[i-1] + dp[i-2] ) % 9901;
        }
        System.out.println(dp[n] % 9901);
    }
}

 

규칙을 통해 이차원배열로 풀었다. 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        final int MOD = 9901;

        long[][] dp = new long[n+1][3]; // i번째 줄에서, j번째 칸에 사자를 놓을 수 있는 경우의 수

        dp[1][0] = dp[1][1] = dp[1][2] = 1;
        
        for(int i=2; i<=n; i++){
            dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % MOD; // 어느칸에도 놓지 않으면 그 전 줄은 영향을 안받음
            dp[i][1] = (dp[i-1][0] + dp[i-1][2]) %MOD; // 1번째 칸에 놓는다면 그 전 줄 아무칸도 놓지 않는 경우 + 전 줄 2번째 칸에 놓는 경우
            dp[i][2] = (dp[i-1][0] + dp[i-1][1]) %MOD; // 2번째 칸에 놓는다면 그 전 줄 아무칸도 놓지 않는 경우 + 전 줄 1번째 칸에 놓는 경우
        }

        long answer =0;
        for(int i=0; i<3; i++){
            answer+=dp[n][i];
        }
        System.out.println(answer % MOD);
    }
}

 

다른 풀이를 보니 이차원 배열로 아무 칸에 놓지 않는 경우, 첫번째 칸에 놓는 경우, 두번째칸에 놓는 경우를 표현할 수 있었다.