[BAEKJOON] 11726번 : 2xn 타일링 (JAVA)

- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식

- 사용 언어 : JAVA

- 문제 요점

1. 높이가 2로 고정, 넓이가 N인 타일의 경우의 수를 도출
2. N이 1일 수도 있으니, 예외 처리 필요
3. 10007로 나누는 거 잊지 않기

- 점화식 도출 

d[i] = d[i-1]+d[i-2];

2x1, 1x2의 2종류 타일이 존재한다.

→ 최대 2칸 전까지만 확인

1. 현재 기준 2칸 전까지 다 채워진 경우 1*2 타일 2개 채움

(2*1 타일 2개로도 채울 수 있지만, 그렇게 되면 2번과 같은 모양)

2. 현재 기준 1칸 전까지 다 채워진 경우 2*1 타일 1개 채움

 

소스 설명은 주석을 참고해주세요.

 

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[] d = new int[N+1];
		
		// 2x1 공간은 2x1타일만 들어가므로 1가지 경우임
		d[1] = 1;
		
		// N이 1일 수도 있으니 조건문으로 예외처리
		if(N>1)
			// 2x2 공간은 2x1타일 2개, 1x2타일 2개로 2가지 경우임
			d[2] = 2;
		
		// 점화식 및 메모이제이션을 이용해 풀이
		for(int i=3; i<=N; i++) {
			// Integer의 최대값을 벗어나 배열에 들어갈 수 있기에, 배열 저장 전에 10007을 나누어 대입
			d[i] = (d[i-1] + d[i-2])% 10007;
		}
		
		// 출력
		System.out.println(d[N]%10007);
		
	}

}