백준 1309 / 동물원

문제

풀이

설명

가로 두칸 세로 n칸으로 사자를 배치하되 사자들은 세로 가로로 서로 붙어 있으면 안 된다.

D[N][0] = N번 줄에 배치하지 않음
D[N][1] = N번 줄의 왼쪽에만 배치함
D[N][2] = N번 줄의 오른쪽에만 배치함

D[N][0] = D[N][0] + D[N][1] + D[N][2] (세가지 다 올 수 있다.)
D[N][1] = D[N][0] + D[N][2] (1에 들어갈 경우 비거나 2에 들어갈 수 있다.)
D[N][2] = D[N][0] + D[N][1] (2에 들어갈 경우 비거나 1에 들어갈 수 있다.)

코드

import java.util.Scanner;

public class Num15988 {

	public static void main(String[] args) {
		
		 Scanner sc = new Scanner(System.in);
		 
	        int n = sc.nextInt();
	        int[][] d = new int[n+1][3];
	        d[0][0] = 1;
	        
	        for (int i=1; i<=n; i++) {
	            d[i][0] = d[i-1][0] + d[i-1][1] + d[i-1][2];
	            d[i][1] = d[i-1][0] + d[i-1][2];
	            d[i][2] = d[i-1][0] + d[i-1][1];
	            for (int j=0; j<3; j++) {
	                d[i][j] %= 9901;
	            }
	        }
	        
	        System.out.println((d[n][0] + d[n][1] + d[n][2])%9901);
	}

}

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/1309