백준 11727번 2 * n 2(java)

1.문제

https://www.acmicpc.net/submit/11727/81385278

2.풀이

처음에 규칙성을 찾기 위해 그려보는 와중에 문제를 잘못 이해해 가로의 경우 뿐 아니라 세로의 경우도 포함해야한다 생각해 * 2를 해서 오래걸렸던 문제다.

2 2 일때는 3개
2 3 일때는 5개가 나오며
2 4 일때는 11개가 나오는데
11개라는 숫자를 만들기 위해서 규칙성을 찾아보면 11 = 5 + 6(3 2) 라는 걸 발견할 수 있었다. 5개에도 확인해본 결과 5 = 3 + 2(1 * 2) 라는 걸 확인했다.

3.코드

import java.io.*;

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[1001];
        dp[1] = 1;
        dp[2] = 3;
        dp[3] = 5;

        for (int i = 4; i <= n; i++) {
            dp[i] = (dp[i - 1] + (2 * dp[i - 2])) % 10007;
        }

        System.out.println(dp[n]);
    }
}