[java 백준] 실버 1 /1309번 동물원

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
 
    public static int n;
    public static long dp[][];
 
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        dp=new long[n+1][3];
        
        //dp[1][0] --> 첫번째 줄에 아무것도 놓지 않는 경우
        //dp[1][1] --> 첫번째 줄에 첫번째 칸에 놓는 경우
 
        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])%9901;
            dp[i][1]=(dp[i-1][0]+dp[i-1][2])%9901;
            dp[i][2]=(dp[i-1][0]+dp[i-1][1])%9901;
        }
        long ans=dp[n][0]+dp[n][1]+dp[n][2]%9901;
        System.out.println(ans%9901);
 
 
 
 
    }
 
 
}

 

 

dp 문제를 푸는건 아래에서 위를 바라보면서 누적합을 해주는 것인데..! 

이 문제는 이렇게 누적합 하는거 까지는 똑같은데 아무것도 놓지 않을 때 개수를 세주기 때문에 이걸 주의해야한다.

나는 한마리도 놓지 않는다는게 2*n칸 모두에 아무것도 놓지 않는 것인줄 알았는데 한줄에 사자를 하나도 놓지 않는경우를 생각해야한다. (1번째칸에 놓고 2번째 칸에 안놓거나  -->dp[n][1]  1번째 칸에 안놓고 2번째 칸에 놓는 것--> dp[n][2]은 너무 당연하기 때문이다. 왜냐면 가로로도 세로로도 붙어있게 배치할 수 없기 때문이다!!)

 

dp[1][0]은 첫째줄에 아무것도 놓지 않는 경우니까 1

dp[1][1] 은 첫째줄 첫번째 칸에만 놓는 것이기 때문에 1

dp[1][2]은 첫째줄 두번째 칸에만 놓는것이기에 1

 

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

dp[2][1]=dp[1][0]+dp[1][2]  (dp[1][1]을 더한다면 세로로 붙어있게 될 것)

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

 

이다. 앞서 말했던 아래에서 위를 보고 누적합을 해준다는 것은  2번째 행의 dp를 구할 때 1번째 줄의 dp값을 바라보며 가로, 세로로 붙어있지 않게끔 1번째 줄의 dp값들을 더해주는 것을 말한다.