👨‍💻 문제

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

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

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

⌨️ 입력

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

🖨️ 출력

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

📖 예제

입력

4

출력

41

---

✍️ 풀이

📘 Cases 클래스

가로가 2칸인 우리에서 각 행마다의 상태는 아래와 같이 3가지의 상태를 가질 수 있다.

• ⬜⬜ : 양쪽 모두 사자가 없는 상태
• 🦁⬜ : 왼쪽에 사자가 존재하는 상태
• ⬜🦁 : 오른쪽에 사자가 존재하는 상태

private static class Cases {

    private final int noLion;
    private final int lionOnLeft;
    private final int lionOnRight;
    
    public Cases(int noLion, int lionOnLeft, int lionOnRight) {
        this.noLion = noLion % 9901;
        this.lionOnLeft = lionOnLeft % 9901;
        this.lionOnRight = lionOnRight % 9901;
    }

🧮 DP

getNextCases() 메소드는 현재 상태로부터 다음 상태를 측정해 새로운 Cases 객체를 반환한다.

    public Cases getNextCases() {
        int nextNoLion = noLion + lionOnLeft + lionOnRight;
        int nextLionOnLeft = noLion + lionOnRight;
        int nextLionOnRight = noLion + lionOnLeft;
        return new Cases(nextNoLion, nextLionOnLeft, nextLionOnRight);
    }
    
    public int getEntireCasesCount() {
        return (noLion + lionOnLeft + lionOnRight) % 9901;
    }
}

첫 번째 행을 (1,1,1)로 초기화하고 getNextCases() 메소드를 통해 n번째 행까지 채운다.

private static void dp() {
    cases = new Cases[n];
    cases[0] = new Cases(1,1,1);
    
    for (int i=1; i<n; i++) {
        cases[i] = cases[i-1].getNextCases();
    }
}

마지막 인덱스의 Cases의 총합이 모든 경우의 수가 된다.

public static void main(String[] args) throws IOException {
    input();
    dp();
    System.out.println(cases[n-1].getEntireCasesCount());
}

---

📄 전체 소스코드

import java.io.*;
import java.util.*;

public class Main {

    private static class Cases {
    
        private final int noLion;
        private final int lionOnLeft;
        private final int lionOnRight;

        public Cases(int noLion, int lionOnLeft, int lionOnRight) {
            this.noLion = noLion % 9901;
            this.lionOnLeft = lionOnLeft % 9901;
            this.lionOnRight = lionOnRight % 9901;
        }

        public Cases getNextCases() {
            int nextNoLion = noLion + lionOnLeft + lionOnRight;
            int nextLionOnLeft = noLion + lionOnRight;
            int nextLionOnRight = noLion + lionOnLeft;
            return new Cases(nextNoLion, nextLionOnLeft, nextLionOnRight);
        }

        public int getEntireCasesCount() {
            return (noLion + lionOnLeft + lionOnRight) % 9901;
        }
    }

    private static int n;
    private static Cases[] cases;

    public static void main(String[] args) throws IOException {
        input();
        dp();
        System.out.println(cases[n-1].getEntireCasesCount());
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
    }

    private static void dp() {
        cases = new Cases[n];
        cases[0] = new Cases(1,1,1);

        for (int i=1; i<n; i++) {
            cases[i] = cases[i-1].getNextCases();
        }
    }
}

---