[알고리즘] - 백준 1309번 : 동물원 (JAVA)

🎯 문제

문제 풀러가기

🎯 입력,출력

🚀 풀이 방법

동적 계획법을 적용해 나갈 배열을 어떤 식으로 구성할 지가 이 문제의 핵심입니다.
저는 이차원 배열의 형태를 생각하였고,
dp[n][0]은 사자가 n행에 어느 곳에서도 위치하지 않을 때
dp[n][1]은 사자가 n행에 왼쪽에 위치 해 있을 때
dp[n][2]는 사자가 n행에 오른 쪽에 위치 해 있을 때로 생각 하였습니다.

한 사이클 마다, dp[n][0], dp[n][1], dp[n][2]에 사자가 있을 경우의 수를 더해가는 것이 핵심 입니다.

1. 사자가 n행에 있지 않을 경우에는, 전 행에서 어느 곳에서나 사자가 위치 해도 되기 때문에
   dp[n][0]=dp[n-1][0]+dp[n-1][1]+dp[n-1][2]

2. 사자가 n 행 왼쪽에 있을 경우에는, 전 행에서 사자가 오른 쪽에 있어야 하거나 있지 않아야 합니다.
   dp[n][1]=dp[n-1][2]+dp[n-1][0]

3. 사자가 n 행 오른 쪽에 있을 경우에는 , 전 행에서 사자가 왼 쪽에 있어야 하거나 있지 않아야 합니다.
   dp[n][2]=dp[n-1][1]+dp[n-1][0]

🚀 CODE

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n;
    static int[][] dp;

    public static void main(String[] args) throws Exception{
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();

        dp=new int[n+1][3];
        Arrays.fill(dp[1],1);

        for(int i=2;i<=n;i++){
            dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
            dp[i][1]=dp[i-1][2]+dp[i-1][0];
            dp[i][2]=dp[i-1][1]+dp[i-1][0];
            dp[i][0] %= 9901;
            dp[i][1] %= 9901;
            dp[i][2] %= 9901;
        }

        int res=0;

        for(int i =0; i<3; i++){
            res+=dp[n][i];
        }

        System.out.println(res%9901);

    }
}

🌟 정답

😍 이상으로 포스팅을 마치겠습니다. 감사합니다 :)