[백준] 동물원 (JAVA)

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

설명

2 * n 우리에 사자들을 넣어야 한다

사자는 가로 세로 이웃하게 위치하면 안된다 대각은 됨(0마리 배치도 가능)

사자를 배치할 수 있는 최대 경우의 수를 9901로 나눈 나머지를 반환하시오

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

/*
백준 1309 동물원
가로 2칸, 세로 n칸인 우리에 사자들을 배치해야 함
사자들을 배치할 수 있는 모든 경우의 수를 9901로 나눈 나머지 반환(0마리도 가능)
dp 문제이다 메모이제이션 활용
점화식이 존재한다
dp[1] = 3
dp[2] = 7
dp[3] = 17
dp[4] = 41
즉 dp[i] = 2 * dp[i-1] + dp[2]이라는 점화식이 나온다
 */
public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int[] dp;

    public static void main(String[] args) throws Exception {
        int n = Integer.valueOf(br.readLine());

        dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 3;

        for (int i = 2; i < n + 1; i++) {
            // 9901로 나눈 나머지
            dp[i] = (2 * dp[i - 1] + dp[i - 2]) % 9901;
        }

        bw.write(dp[n] + "\n");
        bw.flush();
        bw.close();
    }
}

2 * 1, 2 * 2, 2 * 3까지는 경우의 수를 직접 그려서 구해보길...

dp 문제다

그래서 2 * 3까지 직접 그려서 풀어보면

• 2 * 1의 경우: 3가지
• 2 * 2의 경우: 7가지
• 2 * 3의 경우: 17가지

이렇게 나온다

2 * 4는 문제에서 41가지라고 보여준다

이 패턴을 이용해 점화식을 구해보겠다

dp[i] = 2dp[i - 1] + dp[i - 2]

가 나온다

이 점화식을 대입해서 메모이제이션 배열을 선언해서 풀면 된다

그리고 빼먹지 말고 9901의 나머지로 반환해주도록 하자

 

https://github.com/qTeTp/Algo/tree/74dbb9ee5d91ad6bb7ac72fdc3688ffd0a47167a/%EB%B0%B1%EC%A4%80/Silver/1309.%E2%80%85%EB%8F%99%EB%AC%BC%EC%9B%90

Algo/백준/Silver/1309. 동물원 at 74dbb9ee5d91ad6bb7ac72fdc3688ffd0a47167a · qTeTp/Algo