[백준] 2XN 타일링 (java) Dynamic_programming

2020-02-12

2XN 타일링 (백준 > 11726 > Dynamic_programming)

문제 링크

문제설명

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

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

img

입력

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

출력

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

예제 입력 1

2

예제 출력 1

2

풀이

package Dynamic_programming;

import java.util.Scanner;

public class beak_2xn타일링 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		//[n+1]로 하지말고 [1001]로 해야 런타임 에러 안남!
		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]%10007);
	}
}


후기 (40min)

두번째 푸는 건데도 어려워하는 클라스…

dp스러운 문제가 뭔지 알아가는거 같기도, 모르는거 같기도…!


tip

  1. 복습만이 살 길…

참고 블로그 https://lmcoa15.tistory.com/5