[백준] 11726: 2xn타일링

'11726- 2xn타일링' 문제로 이동!

👉문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

👉입력

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

예시 - 9

👉출력

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

예시 - 55

---

✍내 풀이

import java.util.*;

public class Main {

	static int[] arr = new int[1001];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		arr[0] = 0;
		arr[1] = 1;
		arr[2] = 2;
		System.out.println(tiling2n(n));
	}
	
	static int tiling2n(int n) {
		for( int i = 3 ; i <= n ; i++) {
			arr[i] = (arr[i-1] + arr[i-2])%10007;
		}
		return arr[n];
	}
}

---

✍Note

• 점화식 찾기

대부분의 동적계획법은 점화식을 찾으면 해결된다는 글을 보고 대입때 수리논술을 공부할 때처럼 숫자를 나열해보고 점화식을 찾았음.
찾은 식은 arr[i] = arr[i-1] + arr[i-2] 으로 피보나치와 같은 식!

다른 사람들은 어떻게 풀었나 확인하던 도중

가로가 i-1일 경우의 앞부분에 2x1짜리 하나를 붙이는 방법 ( arr[i-1] )
+가로가 i-2일 경우의 앞부분에 1x2짜리 두개를 붙이는 방법 ( arr[i-2] )

로 분할하여 문제를 푸신 분이 계셨다.
내가 푼건 너무 수를 위주로 때려맞춘 것 같고 이렇게 경우를 나누어서 생각해야할 듯 싶음,,

• 문제 제대로..

근데 그냥 이렇게 제출했더니 런타임에러가 나서 뭐지 하고 문제를 다시 읽어보니
2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력
하는 거였음,,😭