[백준] 1309번. 동물원(JAVA)

문제

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

---

풀이(18분)

import java.io.*;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        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]);


    }
}

 

문제를 처음 보고서 규칙을 찾아보려고 했다.

-> 이 과정이 그리디 문제이거나 dp문제일 가능성이 높다는 것이다!!

 

그렇기에 문제에서 제시된 n = 4까지의 상황을 직접 탐색해 보았다.

(1) n = 1 일 때

0 : 1,

1 : 1 + 1로 총 3가지이다.

 

(2) n = 2 일 때

0 : 1,

1 : 1 + 1 + 1 +,

2 : 1 + 1 로 총 7가지

 

(3) n = 3 일 때

0 : 1,

1 : 1 * 6

2 : 3 + 3 + 2(n=2일 때와 동일),

3 : 1 + 1 로 총 17가지

 

(4) n = 4 일 때

0 : 1,

1 : 1* 8

2 : 5 + 5+ 8(n=3일 때와 동일),

3 : 3 + 3 + 2 + 2 + 1 + 1,

4: 1 + 1 로 총 41가지이다.

 

dp라는 것을 인식했기에 과정을 밟아갈 때 점화 식 같아 보이는 부분은 체크하면서 넘어가자.

 

하지만 내가 규칙을 찾을 때는 위에 괄호표를 해둔 것을 제외하면 별다른 부분을 인식하지 못했다.

그럼 각 하나씩의 규칙을 찾아보자!!! -> 이것도 별다르게 찾지 못했다.

그럼 전체적인 숫자에 대한 규칙을 찾아보자!! -> 아 이전 인덱스 값의 2배에 (인덱스-2)의 값을 더하면 되네!

-> 이 생각이 들었다면 n = 5일 때도 직접 생각해 보자!! 여기까지 통과했다면 맞을 가능성이 높다.

 

물론 정확한 규칙을 찾았다고 하기는 어렵지만 n=3, n= 4, n=5에서 3번의 검증을 거쳤다면 맞을 수 있을 것이다.

예제가 통과했다고 냅다 제출하지 말고, 내가 해야 할 것은 두 가지이다.

1. 정말 완벽한 규칙을 찾아 내가 세운 식이 맞나 검증한다.

2. n = 5 일 때를 손으로 직접 해보고(잘못 카운트할 가능성 있으니 주의) 점화식이 맞나 보자.

 

1이 어려워서 2로 진입했고 통과했다!