[DP] 백준 1309번 동물원 - JAVA

 

 

오랜만에 시간초로 낚인 문제가 있었으니...

바로 동물원...

 

2초라는 시간대가 여유롭다고 착각하고,

PowerSet으로 돌렸다가 N=100000이 시간초과로 안돌아가는 상황을 목격했다.

충격~

 

15초 내로 N=21까지만 돌아간다 ㅋㅋ

그래서 아... 이거 DP였구나를 깨달아버렸다.

 

 

---

1. 출처

---

 

 

1309번: 동물원

 

• N이 주어진다. N은 행이다.
• 열은 2로 고정이다
• (N,2) 행렬에서 사자를 우리에 넣을 수 있는 경우의 수를 구하는 것
• 한 사자를 넣을 때 근접한 가로, 세로에 사자가 들어있으면 그 위치에 사자를 넣을 수 없음 (4방 탐색)

 

 

---

2. 설계

---

 

그래서 DP면 공식이 뭐지?...

이중그래프를 그려놓고, 한칸 한칸 씩 나올 수 있는 수를 써보았다.

 

 

 

N=1일 때, [0][0] 자리만 있다고 가정하면 {공집합, [0][0]}}의 경우의 수 2가지가 있다.

N=1일 때, [0][0]~[0][1] 자리가 있다고 가정하면 {공집합, [0][0]. [0][1]}의 경우의 수 3가지가 있다.

 

 

 

N=2일 때, [0][0]~[1][0] 자리가 있다고 가정하면

 

1)

X O

O

 

2)

X X

O

 

이 2가지 경우가 있어 총 5가지 경우가 나올 수 있다.

 

 

N=2일 때, [0][0]~[0][2] 자리가 있다고 가정하면

 

1)

O X

X O

 

2)

X X

X O

 

이 2가지 경우가 있어 총 7가지 경우가 나올 수 있다.

 

 

이런식으로 N=3까지를 했을 때 나는 규칙을 발견했다.

 

 

[r][0]의 자리를 구할 때는 [r-1][0] + [r-1][1]을 더한 값과 같았고,

 

 

 

[r][1]의 자리를 구할 때는 [r-1][0] + [r][0]을 더한 값과 같았다.

 

 

테스트케이스로 주어진 N=4의 값도 위 방식대로 하면 41이 나온다는 것을 확인할 수 있다!

 

 

---

3. 정답 코드 (DP)

---

import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int dp[][] = new int[N][2];
        dp[0][0] = 2;
        dp[0][1] = 3;

        for(int r=1; r<N; r++){
            for(int c=0; c<2; c++){
                if(c==0) dp[r][c] = (dp[r-1][0] + dp[r-1][1])%9901;
                if(c==1) dp[r][c] = (dp[r-1][0] + dp[r][0])%9901;
            }
        }

        System.out.println(dp[N-1][1]);
    }
}

 

 

 

 

---

4. 오답 코드 (PowerSet)

---

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

class Main {

    static int N;
    static boolean[][] cage;
    static int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
    static int count;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        cage = new boolean[N][2];
        PowerSet(0);

        System.out.println(count);
    }

    public static void PowerSet(int depth){
        if(depth == N){
            count = (count+1)%9901;
            return;
        }

        if(IsPossible(depth, 0)){
            cage[depth][0] = true;
            PowerSet(depth+1);
            cage[depth][0] = false;
        }

        if(IsPossible(depth, 1)){
            cage[depth][1] = true;
            PowerSet(depth+1);
            cage[depth][1] = false;
        }

        PowerSet(depth+1); //아무것도 선택 안함

    }

    public static boolean IsPossible(int row, int col){
        for(int d=0; d<4; d++){
            int nextR = row+drc[d][0];
            int nextC = col+drc[d][1];

            if(nextR<0 || nextR>=N || nextC<0 || nextC>=2) continue;
            if(cage[nextR][nextC]) return false;
        }

        return true;
    }
}

 

15초 내로 N=21밖에 안돌아감