[백준] 11726번 : 2×n 타일링

11726번: 2×n 타일링

---

문제

---

풀이

2 * N 의 경우의 수는 2 * (N - 1)의 경우의 수와 2 * (N - 2)의 경우의 수의 합과 같다.

즉, 배열을 생성하여 2 * 1일때는 1개의 경우의 수와 2 * 2일때는 2개의 경우의 수가 있으니 배열에 넣어주고,

반복문을 통해서 i를 3부터 시작하여  i - 2와 i -1을 더한값을 arr[i]에 넣어주면 된다.

여기서 주의할 점은 연산할 때마다 mod 연산을 해주어야 한다.

계속 숫자를 더하고 마지막 출력시에만 mod연산을 해줄 경우 Integer.MAX_VALUE를 넘어 Overflow가 발생하기 때문에 잘못된 값이 출력될 수 있다.

---

소스 코드

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

        int N = Integer.parseInt(br.readLine());

        int[] DP = new int[1001];
        DP[1] = 1;
        DP[2] = 2;

        for (int i = 3; i <= N; i++) {
            DP[i] = (DP[i - 1] + DP[i - 2]) % 10007;
        }

        System.out.println(DP[N]);
    }
}

---

참고

[백준] 11726번: 2×n 타일링 - JAVA