백준 1309 동물원 (Java)

1. 문제 링크

1309번: 동물원

 

2. 문제 및 입출력예제

 

3. 문제 풀이

조금 잘 생각해야 하는 dp문제였다.

dp[i-1]에 사자가 왼쪽, 오른쪽 있다는 생각으로 dp[i-1]*2에

dp[i-2]를 더했다.

나머지 연산을 한 상태로 dp에 저장해야 한다.

점화식: dp[i] = (dp[i-1]*2 + dp[i-2]) % 9901

 

4. 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] dp = new int[N+1];
		dp[0] = 1;
		dp[1] = 3;
		for(int i=2;i<N+1;i++) {
			dp[i] = (dp[i-1]*2 + dp[i-2]) % 9901 ;
		}
		System.out.println(dp[N]);
	}
}