[백준 *Java] - 동물원 (1309)

동물원 문제보기

1309번: 동물원

 

문제 설명
어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.
이 동물원에는 사자들이 살고있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다.
이 동물원 조련사는 사자들의 배치 때문에 골머리를 앓고 있다.

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

입력
첫째 줄에 우리의 크기 N(i <= N <= 100,000)이 주어진다.

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

 

N이 1일 때, 3개

N이 2일 때, 7개

N이 3일 때, 17개

테스트케이스에서 나온 N이 4일 때, 41개

이렇게 나열하고 규칙을 찾으니,

DP[N] = DP[N-1] * 2 + DP[N-2] 라는 점화식이 나왔습니다.

 

아래는 구현한 성공한 코드입니다.

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

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

        DP = new long[N+1];
        DP[0] = 1;
        DP[1] = 3;
        for (int i = 2; i < DP.length; i++) {
            long a = DP[i-1];
            long b = DP[i-2];
            DP[i] = (a * 2 + b) % MOD;
        }

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

 

주의)

여기서 문제에서 N이 1부터 10만까지라고 했는데,

초기화를 DP[2]까지 해주고, for문을 3부터 돌게되면 ArrayIndexOutofBound 라는 에러가 뜹니다.

why? 1을 넣을 때, DP[2]를 초기화시킬 수 없어서 error가 발생합니다.

..이것 때문에 계속 런타임 오류가 떠서, 글로 남깁니다.