백준 / 11726번 / 2×n 타일링

[문제]

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

[입력]

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

[출력]

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

[예제 입력]

2

[예제 출력]

2

[예제 입력]

9

[예제 출력]

55

 

---

 

어떻게 풀어야하나 고민을 해보다가, 잘 모르겠어서

n=5인 경우까지 직접 그림을 그리며 풀어봤다.

풀어보니, 패턴이 보였다!

 

arr[n] = arr[n-2] + arr[n-1] 이란 패턴이 반복된다.

 

주의해야 할 점은 n까지 모두 값을 위의 패턴대로 구한 후 마지막에 arr[n]%10007을 출력하면

Integer 범위를 벗어나기 때문에 저장 할 때 마다 나머지를 저장하는 방법을 사용해야 한다.

 

또한,

처음 arr 배열을 생성할 때 습관처럼 new int[n+1]로 생성을 했는데, 이 경우엔  ArrayIndexOutOfBounds 오류가 뜬다.

이유는, arr[1]과 arr[2]는 for문을 돌지않고 초기화를 해주는데 입력값 n이 1인 경우에 배열 인덱스를 벗어나기 때문이다!

 

1001로 생성하거나, n+2로 생성하면 된다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int arr[] = new int[1001];

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

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