[JAVA/DP] 동물원_1309

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

1309번: 동물원

 

 

동물원 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

28076

13855

10970

47.518%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

4

예제 출력 1 복사

41

출처

• 문제의 오타를 찾은 사람: joon8409
• 문제를 만든 사람: xhark

알고리즘 분류

• 다이나믹 프로그래밍

 

 

 

import java.util.Scanner;


public class Main
{
	
    private static Scanner s = new Scanner(System.in);
    
    public static void main(String[] args) {
    	
    	// 결국 여느 DP랑 똑같이 법칙을 찾는 문제.
    	/*
    	 * N=1 일 경우 정답은 3이 됨. (한 마리 2 / 0 마리 1)
    	 * N=2 일 경우 정답은 7 (두 마리 2 / 한 마리 4 / 0 마리 1)
    	 * N=3 일 경우 정답은 17 (세 마리 2 / 두 마리 8 / 한 마리 6 / 0 마리 1)
    	 * N=4 일 경우 41 (예시에 써있음.)
    	 * 
    	 * 즉, N=0 은 1로 봤을 때
    	 * N = (N-1)*2 + (N-2) 라는 규칙을 찾을 수 있음.
    	 */
    	
    	int N = s.nextInt();
    	long[] answer = new long[N+1];
    	
    	answer[0] = 1;
    	answer[1] = 3;
    	
    	for(int i=2; i<=N; i++) {
    		answer[i] = (answer[i-1]*2 + answer[i-2]) % 9901;
    	}
    	
    	System.out.println(answer[N]);
    	
    }
    
}