[BOJ] 1309 : 동물원 [S1]

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

1309번: 동물원

 

 

[문제]

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

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

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

[입력]

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

[출력]

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

[예제 입력 1]

4

[예제 출력 1]

41

 

 

[내 풀이]

다이나믹 프로그래밍(dp)를 이용하여 풀었습니다.

2차원 배열 animal의 0열과 1열은 각 열에 동물이 위치할 경우의 수를 카운팅 해주었고, 2열은 해당 행에 동물이 위치하지 않을 경우를 카운팅 해주었습니다.

 

N의 크기가 1부터 100,000까지여서 N이 커지게되면 수의 범위를 넘어서게 됨을 방지하기 위해, 출력시 9901로 나눈 나머지를 출력하는 것을 확인한 후 모듈러 산술을 이용하여 ans배열에 항상 9901로 나눈 나머지를 넣었습니다.

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

/*
	문제 : [S1] 동물원 - 1309번
	제출 : 2024년 1월 31일
	결과 : 통과
	성능 요약 : 메모리 18048KB, 시간 144ms
	아이디어 : N*3의 2차원 배열을 만들어 3번째 열에는 그 행에 동물이 오지 않을 경우를 체크해주었습니다.
*/
public class BOJ_1309_동물원 {

	static int[][] animal;
	static int[] ans;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		animal = new int[N][3];
		ans = new int[N];
		// 0행 0열에 동물 위치할 경우의 수
		animal[0][0] = 1;
		// 0행 1열에 동물 위치할 경우의 수
		animal[0][1] = 1;
		// 0행에 동물이 위치하지 않을 경우의 수
		animal[0][2] = 1;
		ans[0] = 3;
		for (int i=1; i<N; i++) {
			animal[i][0] = (animal[i-1][1] + animal[i-1][2]) % 9901;
			animal[i][1] = (animal[i-1][0] + animal[i-1][2]) % 9901;
			animal[i][2] = (animal[i-1][0] + animal[i-1][1] + animal[i-1][2]) % 9901;
			ans[i] = (animal[i][0] + animal[i][1] + animal[i][2]) % 9901;
		}
		System.out.println(ans[N-1]);
	}
}