[백준] 동물원 (1309번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습)

[백준] 동물원 (1309번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습)

---

[접근 방법]

 

우리의 크기가 2*i 인 배열에 사자를 배치하는 경우의 수를 저장한 배열

DP[i] 라 할때,

 

DP[1] = 3

DP[2] = 7

DP[3] = 17

DP[4] = 41

 

DP[0] = 1이라 하면,

 

(i >= 2) 에 대하여,

DP[i] = DP[i-1] * 2 + DP[i-2] 

가 성립한다.

 

너무 때려 맞춘 느낌이 강하게 들어서 기분이 좋진 않다.

---

[JAVA 코드]

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

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 우리의 크기 (1≤N≤100,000)
        int N = Integer.parseInt(br.readLine());

        // 0 ~ N
        int[] DP = new int[N+1];
        DP[0] = 1; // 우리가 없는 경우 / 어떠한 사자도 재치하지 않는 경우 : 1
        DP[1] = 3; // (0 , 0) , (1 , 0) , (0 , 1)로 사자를 배치하는 경우 : 3

        // 점화식 : dp[N] = dp[N-1] * 2  + dp[N-2]
        for(int i=2; i<=N; i++)
        {
            DP[i] = (DP[i-1] * 2 + DP[i-2]) % 9901;
        }

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

 

 

+) 다른 방법

 

DP[i][j] : i번째 줄의 j번째 칸에 놓을 수 있는 경우의 수

로 정의 하여 전수조사 하는 방법이 존재한다.

1. 첫번째 줄에 아무런 동물을 놓지 않는 경우 

2. 첫번째 줄, 첫번째 칸에 동물을 놓는 경우

3. 첫번째 줄, 두번째 칸에 동물을 놓는 경우

 

1, 2, 3의 경우를 모두 더하여 답을 도출한다.

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

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 우리의 크기 (1≤N≤100,000)
        int N = Integer.parseInt(br.readLine());

        // DP[i][j] : i번째 줄의 j번째 칸에 놓을 수 있는 경우의 수
        // j = 0 : i번째 줄에 아무런 동물 X
        // j = 1 : 첫번째 칸에 동물 O
        // j = 2 : 두번째 칸에 동물 O
        long[][] DP = new long[N+1][3];
        // 첫번째 줄에 모든 경우를 구하기 위해 초기값 설정
        DP[1][0] = DP[1][1] = DP[1][2] = 1; 

        for(int i=2; 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;
        }

        bw.write((DP[N][0] + DP[N][1] + DP[N][2]) % 9901 + "\n");
        bw.flush();
        bw.close();
    }
}