[백준] 1309 동물원 / 자바(Java)

문제

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

1309번: 동물원

 

---

해설

dfs와 같은 탐색으로 해결하기에는 N의 길이가 너무 길다(답을 9901로 나눈 나머지를 출력하라는 부분도 값이 크게 되리라는 예상이 된다)

 

따라서 DP를 사용해 이전의 경우의 수에서 가능한 가능성을 구하는 점화식의 형태로 문제를 해결한다.

 

arr[i][j]에서 i 는 사자우리의 세로번째의 수, j는 0~2까지 각각 사자가 들어가지 않는 경우, 왼쪽칸에 들어간경우, 오른쪽 칸에 들어간 경우를 나타내어 arr[i][j]는 i번째에 각 가능성이 될 경우의 수가 들어가게 된다.

 

사자우리는 바로 이전 번째에서만 영향을 받아 arr[i][0], arr[i][1], arr[i][2]는 모두 arr[i-1]에서만 영향을 받는다.

 

0인 경우는 0, 1, 2 모든 조건에서도 추가가 가능하므로 모두 더해준다.

1인 경우는 0, 2 인 조건에서만 추가가 가능하므로 arr[i-1][0], arr[i-1][2]을 더해준다.

2인 경우는 0, 1 인 조건에서만 추가가 가능하므로 arr[i-1][0], arr[i-1][1]을 더해준다.

 

최종적으로 시작 번호가 0부터 시작했으므로 i-1번째의 세 요소를 모두 더해 9901로 나눈 나머지가 해답이 된다.

주의점

• N 은 최대 100,000. 직접 다 구하기는 시간이 초과된다.

---

코드

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		// 0,0   1,0   0,1
		int arr[][] = new int [N][3];
		arr[0][0] = 1;
		arr[0][1] = 1;
		arr[0][2] = 1;
		
		for(int i=1;i<N;i++) {
			arr[i][0] = (arr[i-1][0]+arr[i-1][1]+arr[i-1][2])%9901;
			arr[i][1] = (arr[i-1][0]+arr[i-1][2])%9901;
			arr[i][2] = (arr[i-1][0]+arr[i-1][1])%9901;
		}
		
		int ans = arr[N-1][0]+arr[N-1][1]+arr[N-1][2];
		System.out.println(ans%9901);
		sc.close();
	}
}