[백준 알고리즘] 백준 1309번 동물원 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 1309번 동물원 자바(Java)

1) 문제번호 : 1309번

 

2) 문제 출처

www.acmicpc.net/problem/1309

1309번: 동물원

 

2. 문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다. 

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

 

3. 제약사항

- 

4. 입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

 

5. 출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

 

6. 풀이

- DP 배열에서 맨 처음 열에 사자가 있는 것으로 정의하고 시작

- 1번째 열 0,1,2 번째 칸에는 1씩 넣어져 있는데, 3가지 상황을 고려해야 한다.

- 사자가 i 번째 줄에 없어도 되는 경우

- i번째 1번째 칸에 사자가 있는 경우

- i번째 줄에 2번째 칸에 사자가 있는 경우

 

- 이 경우들에 대해서 규칙을 찾으면 된다.

 

7. 소스 코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 우리의 크기
		int[][] DP = new int[N+1][3];
		
		//사자가 첫 열에 있는 경우 시작
		DP[1][0] = 1;
		DP[1][1] = 1;
		DP[1][2] = 1;
	
		//
		for(int i=2;i<=N;i++) {
			//사자가 i 번째 줄에 없어도 되는 경우
			DP[i][0] = (DP[i-1][0] + DP[i-1][1] + DP[i-1][2]) % 9901;
			
			//i번째 1번째 칸에 사자가 있는 경우
			DP[i][1] = (DP[i-1][0] + DP[i-1][2]) % 9901;
			
			//i번째 줄에 2번째 칸에 사자가 있는 경우
			DP[i][2] = (DP[i-1][0] + DP[i-1][1]) % 9901;
		}
		
		System.out.println((DP[N][0] + DP[N][1] + DP[N][2])%9901);
	}
}

 

---