[백준, 자바] 11726번 - 2*n 타일링

문제 링크
https://www.acmicpc.net/problem/11726

최종 코드(정답)

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

public class Main_11726 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int j = Integer.parseInt(br.readLine());

        int dp[] = new int[1001]; // j는 1000보다 작거나 같다.

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int k = 4; k <= j; k++) {
            dp[k] = (dp[k - 1] + dp[k - 2]) % 10007;
        }
        System.out.println(dp[j]);
    }
}

틀린 코드

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 j = Integer.parseInt(br.readLine());

        int dp[] = new int[1001]; // j는 1000보다 작거나 같다.

        for (int k = 4; k <= j; k++) {
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 3;

            dp[k] = (dp[k - 1] + dp[k - 2]) % 10007;
        }
        System.out.println(dp[j]);
    }
}

위 코드의 경우 dp[1] = 1; dp[2] = 2; 부분을 for문 안에 넣었더니 오답이란다.

풀이
나는 머리가 나빠서 손으로 해결하려들기에
또 일일이 다 그렸다.

2*1을 구성하는 방법: 1
2*2를 구성하는 방법: 2
2*3을 구성하는 방법: 3
2*4를 구성하는 방법: 5
2*5를 구성하는 방법: 8

다행히 피보나치랑 비슷하구나를 5에서 알아챌 수 있었다.
그러면 동적 프로그래밍 기초 예제로 풀 수 있다.

후기
간만에 머리로 뭔가를 생각해냈나 싶었더니 쓸데없는 이중 for문을 돌린 바람에 k 조건식을 틀려버렸다.

로직은 O(N)으로 풀려 했으면서 왜 이중 for문을 걸었을까...

% 1007 연산을 마지막에 걸면 안된단다. (그거 해서 또 틀림)