백준 동물원

문제

내가 생각했을때 문제에서 원하는부분

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

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

내가 이 문제를 보고 생각해본 부분

BufferedReader를 사용하여 입력을 읽고, 첫 번째 줄에서 정수 N을 읽는다.
이는 우리(격자)의 세로 길이를 나타낸다.
DP 배열 초기화:
dp는 2차원 배열로, dp[i][j]는 i번째 열에서 사자 배치의 상태를 나타낸다.
dp[i][0]: i번째 열에 사자가 없는 경우의 수
dp[i][1]: i번째 열의 첫 번째 줄에 사자가 있는 경우의 수
dp[i][2]: i번째 열의 두 번째 줄에 사자가 있는 경우의 수
초기값 설정:
dp[0][0]은 사자가 없는 경우로 초기값을 1로 설정해준다.
나머지 두 가지 경우는 0으로 설정한다. (0번째 열에는 사자가 있을 수 없음)
동적 프로그래밍 계산:
이 루프는 1부터 N까지 각 열에 대해 가능한 경우의 수를 계산합니다.
사자가 없는 경우 (dp[i][0]):
이전 열의 모든 경우를 더한다.
사자가 첫 번째 줄에 있는 경우 (dp[i][1]):
이전 열에서 사자가 없는 경우와 두 번째 줄에 사자가 없는 경우만 더한다. (사자가 가로로 붙어 있지 않도록 하기 위함)
사자가 두 번째 줄에 있는 경우 (dp[i][2]):
이전 열에서 사자가 없는 경우와 첫 번째 줄에 사자가 있는 경우를 더한다.
결과 계산 및 출력:
마지막 열(N번째 열)의 모든 경우를 더하여 결과를 계산하고, 9901로 나눈 나머지를 출력해준다.

코드로 구현

package baekjoon.baekjoon_25;

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

// 백준 1309번 문제
public class Main872 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // dp 배열 초기화 (N+1 x 3 크기의 2차원 배열)
        long[][] dp = new long[N + 1][3];

        // 초기값 설정
        dp[0][0] = 1;  // 사자가 없는 경우
        dp[0][1] = 0;  // 사자가 있는 경우 (불가능)
        dp[0][2] = 0;  // 사자가 있는 경우 (불가능)

        for(int i = 1; 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 result = (dp[N][0] + dp[N][1] + dp[N][2]) % 9901;
        System.out.println(result);
        br.close();
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.