[백준] code.plus(다이나믹 프로그램 part 2,JAVA)1309번, 동물원

문제 링크

1309번: 동물원

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

다이나믹 프로그램

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

 

동적 계획법 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 2*n의 우리가 존재한다.

2. 사자끼리 인접한 우리에는 살지 못한다.

3. 우리에 사자를 배치할 수 있는 경우의 수를 출력한다.

4. 결과를 출력할 때 9901로 나눈 나머지를 결과로 출력한다.

 

배열

 

DP : 메모이제이션 배열

 

DP[][] 배열을 이용하여 우리에 살 수 있는 사자의 경우의 수를 구하였습니다.

 

우리에 가로열에 사자가 살 수 있는 경우는 3가지가 존재하여 각각의 경우의 수를 따로 저장하였습니다.

 

DP[1][0] = 가로열에 아무 사자도 살지 않는경우

DP[1][1] = 가로열에 왼쪽 우리에 사자가 사는 경우

사자

DP[1][2] = 가로열에 오른쪽 우리에 사자가 사는 경우

사자

 

예제 입력1의 DP표를 표현하면

	1	2	3	합
1	1	1	1	3
2	3	2	2	7
3	7	5	5	17
4	17	12	12	41

 

표를 통해 규칙을 발견할 수 있습니다.

1. DP[i][0] = DP[i-1][0] + DP[i-1][1] + DP[i-1][2]

2. DP[i][1] = DP[i-1][0] + DP[i-1][2]

3. DP[i][2] = DP[i-1][0] + DP[i-1][1]

 

위 규칙이 나오는 이유는

DP[i][0]이면 DP[i-1][0~2]의 모든 경우가 들어갈 수 있기 때문입니다.

아래 표는 DP[i][0]의 기본적인 우리 형태입니다.

사자 없음	사자 없음

 

DP[i][1]이면 DP[i-1][0]와 DP[i-1][2]의 경우만 들어갈 수 있습니다.

 

아래 표를 확인하면 DP[3][1]의 형태는 모두 사자와 인접하게 되기 때문에 DP[i-1][1]을 빼고 더합니다.

DP[3][1]일 때 이곳에 사자가 존재
사자	사자 없음

DP[i][1]이면 DP[i-1][0]와 DP[i-1][1]의 경우만 들어갈 수 있습니다.

아래 표를 확인하면 DP[3][2]의 형태는 모두 사자와 인접하게 되기 때문에 DP[i-1][2]을 빼고 더합니다.

	DP[3][2]일 때 이곳에 사자가 존재
사자 없음	사자

 

DP[4][0] = DP[3][0] + DP[3][1] + DP[3][2] = 7 + 5 + 5 = 17

DP[4][1] = DP[3][0] + DP[3][2] = 7 + 5 = 12

DP[4][2] = DP[3][0] + DP[3][1] = 7 + 5 = 12

모든 경우의 수 : DP[4][0] + DP[4][1] + DP[4][2] = 17 + 12 + 12 = 41

 

모든 경우의 수 41을 결과로 출력합니다.

 

문제에 해결알고리즘은

1. 입력값보다 작은 값들에 대하여 규칙을 적용해서 DP[][]를 구성합니다.

2. DP[n][0] + DP[n][1] + DP[n][2]을 9901로 나눈 나머지를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• DP[1][0~2]의 값을 초기화해주는 init 함수를 만들었습니다.
• 규칙을 적용하여 DP를 구성하는 cal함수를 만들었습니다.
• BufferedWriter에 DP[n][0] + DP[n][1] + DP[n][2] 값을 9901로 나눈 나머지 값을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• cal은 반복문을 통해 위에 설명한 규칙을 적용시켜주었습니다.
• init는 DP[1][0~2]의 값을 초기화해주었습니다.

 

결과 코드

import java.io.*;
public class Main{
	static int[][] DP;		//메모이제이션 배열
	static int DIV = 9901;		//나머지 구하기 위해 나누는 값
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	int N = Integer.parseInt(br.readLine());
    	DP = new int[N+1][3];
    	init();		//DP 초기화 함수 실행
    	cal(N);		//규칙을 통한 DP구성 함수 실행
    	int result = (DP[N][0] + DP[N][1] + DP[N][2])%DIV;	//모든 경우의수 나머지 값 구하기
    	bw.write(result + "\n");		//나머지값 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //DP[1][0~2]의 값 초기화하하는 함수
    static void init() {
    	DP[1][0] = DP[1][1] = DP[1][2] = 1;
    	return;
    }
    //규칙을 통해 DP를 구성하는 함수
    static void cal(int N) {
    	for(int i=2;i<=N;i++) {
    		DP[i][0] = (DP[i-1][0] + DP[i-1][1] + DP[i-1][2])%DIV;	//규칙1.
    		DP[i][1] = (DP[i-1][0] + DP[i-1][2])%DIV;		//규칙2.
    		DP[i][2] = (DP[i-1][0] + DP[i-1][1])%DIV;		//규칙3
    	}
    	return;
    }
}