BOJ) 동물원 (1309, JAVA)

풀이

 

코드 라인을 보면 아주 간단한 문제라고 여겨지겠지만, 점화식을 도출하는 것이 어려웠다.

더 사실대로 말하자면, 혼자 도출하지 못했고 다른 풀이에서 점화식을 얻어왔다고 표현하는게 더 맞는 것 같다.

 

처음에는 Combination과 같은 경우를 찾는 식을 활용하는 방향으로 접근했다.하지만 어떤 식도 부합하는 것이 없었고, n=1 ~ n=4까지 직접 경우의 수를 찾아봤다.

 

n=1 => 3n=2 => 7n=3 => 17n=4 => 41

 

위와 같이 경우의 수가 나왔다.위에서 유추할 수 있는 것은, dp[n] = dp[n-1]*2 + dp[n-2] 라는 식이다.n-1의 경우의 수 *2 + n-2의 경우의 수가 되는데, 왜 이 식이 성립하는지는 아직 명확하지 않다.n이 1씩 증가할 때마다, 2칸이 생기기 때문에, 이전의 경우의 수 *2가 되는 것은 알겠지만, n-2만큼 더해주는 경우를 이해하지 못했다.

 

코드

 

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());
        br.close();
        solution(n);
    }

    private static void solution(int n) {
        final int mod = 9901;
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 3;
        for(int i=2; i<=n; i++)     dp[i] = (dp[i-1] *2 + dp[i-2]) % mod;
        System.out.println(dp[n]);
    }
}