1309.동물원

1. 문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

## 입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

## 출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	32587	15957	12653	47.177%

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

2. 풀이

2.1. 알고리즘 흐름

일단 사자가 들어갈수있는 우리의 세로가 n 이다. 그럼 2xn 개씩 우리가 생성된다.

n = 1 일경우

2x1 의 칸이 생성되고 n의 수에 따라서

arr[n][0] : 두개의 방중에 사자를 아예 넣지 않음.
arr[n][1] : 두개의 방중 왼쪽방에만 사자를 넣음
arr[n][2] : 두개의 방중 오른쪽 방에만 사자를 넣음

그리고 조건은 사자를 넣은방의 옆방과 아래방에는 사자를 넣을수가 없다. 즉 사자를 넣지 않은 경우를 제외하고 n번방에 넣은 곳의 위치에 따라 다음 사자의 위치가 정해진다.

      

      

      

    
    

      <code />
    
dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] //이전방에 사자가 어디있든 상관X
dp[i][1] = dp[i-1][0] + dp[i-1][2] //이전방의 오른쪽, 없는경우
dp[i][2] = dp[i-1][0] + dp[i-1][1] //이전방의 왼쪽, 없는경우

이렇게 3가지 경우로 나눌수있다.

2.2. 코드

      

      

      

    
    

      <code />
    
package 기초1.Day20.정해영;  

import java.util.Scanner;  

public class 동물원 {  

    static int ZERO = 0;  
    static int Left = 1;  
    static int Right = 2;  
    static int MOD = 9901;  

    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  

        int n = sc.nextInt(); //우리의 크기 n  
        long[][] dp = new long[n+1][3];  

        dp[1][ZERO] = 1;  
        dp[1][Left] = 1;  
        dp[1][Right] = 1;  

        for(int i=2; i<=n; i++){  
            dp[i][ZERO] = (dp[i-1][ZERO] + dp[i-1][Left] + dp[i-1][Right]) % MOD;  
            dp[i][Left] = (dp[i-1][ZERO] + dp[i-1][Right]) % MOD;  
            dp[i][Right] = (dp[i-1][Left] + dp[i-1][ZERO]) % MOD;  
        }  

        System.out.println((dp[n][ZERO] + dp[n][Left] + dp[n][Right]) % MOD);  
        sc.close();  
    }  
}

다른 방법(dp를 1차원배열로 선언)

      

      

      

    
    

      <code />
    
import java.io.*;
import java.util.*;

public class Main {
    public static final int MOD = 9901;
    public static int N, dp[];
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        dp = new int[N+1]; //
        dp[0] = 1;
        dp[1] = 3;
        for(int i=2;i<=N;i++){
            dp[i] = ((2 * dp[i-1]) + dp[i-2]) % MOD;
        }

        System.out.println(dp[N]);
    }
}

n = 1 -> 1

n = 2 -> 3

n = 3 -> 17

n = 4 -> 41

      

      

      

    
    

      <code />
    
//점화식
dp[n] = (dp[n-1] x 2) + dp[n-2]