[백준] 1309 동물원 [JAVA]

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

 

1. 정답

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

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int N = Integer.parseInt(br.readLine());
        if (N == 1) {
            System.out.println(3);
            return;
        }
        if (N == 2) {
            System.out.println(7);
            return;
        }

        int[] matrix = new int[N + 1];
        matrix[1] = 3;
        matrix[2] = 7;

        for (int i = 3; i <= N; i++) {
            matrix[i] = (matrix[i - 1] * 2 + matrix[i - 2]) % 9901;
        }

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

 

2. 접근

처음에 문제를 이해하지 못해서 힌트를 보고 풀었다,,,

일단 DP 문제이므로 작은 문제부터 차근차근 생각해보았다

 

1. N=1 일때

N이 1인 경우에는 다음과 같은 3가지 경우가 생길 수 있다.

1. 사자가 없을 때

X

X

 

2. 사자가 왼쪽에 있을 때 , 오른쪽에 있을때

X

O

 

 

2. N=2 일 때

N이 2인 경우에는 다음과 같은 7가지 경우의 수가 생길 수 있다. 

이런 사자우리의 형태에서 n=1일 때를 고려해서 생각해보자

1. 사자가 우리에 없을 때 -> 사자가 2번째 줄에서도 없을수도 있고, 왼쪽에 있을 수도 있고, 오른쪽에 있을 수 있다

2. 사자가 왼쪽 우리에 있을 때 -> 사자가 없을 수도 , 오른쪽에 있을수도

3. 사자가 오른쪽 우리에 있을 때 -> 사자가 없을 수도, 왼쪽에 있을수도

 

3. N=3 일 때

N이 3인 경우에는 다음과 같은 경우의 수가 생길 것이다.

1. 2번째 줄에도 없는 경우 -> 3번째줄에도 없는 경우 , 왼쪽, 오른쪽

2. 2번째 줄의 왼쪽에 있는 경우 -> 사자가 없을 수도, ,,,

 

이런식으로 생각해보면 다음과 같은 식이 나온다

dp[i]= (dp(i-1)*2+dp(i-2))%9901

 

dp(i-1) 

- 이전 줄이 왼쪽 이었다면 -> 없거나, 오른쪽 | 이전 줄이 오른쪽이었다면 -> 없거나, 왼쪽 | 이전 줄이 비어있었다면 -> 왼쪽, 오른쪽

이므로 *2 하여 더해주기 

 

dp(i-2)

- 추가로, 이전 줄을 완전히 비우고, N=1의 상태에서 N=3으로 점프해서 배치하는 경우도 고려해야 하므로

 

%9901: 문제의 조건

 

 

-> dp의 대표적인 유형인 피보나치 수열을 생각하면 비슷한 유형의 문제였다

점화식 도출에 어려움을 겪어서 힌트를 봤지만,,