[백준,BOJ 11726] 2xn 타일링( JAVA 구현)

-내 생각

  우선 DP에 대해서 개념이 없을 때 강의를 보면서 잠깐 풀어봤던 문제로, 다시 풀어 보았다. 

 

-해법

  DP문제의 경우 점화식을 구하기 위한 경우의 수를 잘 계산해야 하는 것 같다. N이 1일 경우 2X1크기의 타일 1개를 배치할 수 있고, 2일 경우 2X1크기의 타일 2개, 1X2크기의 타일 2개로 총 2개의 경우의 수가 존재하게 된다. N이 3일 경우는 N이 1일 경우와 2일 경우의 타일 배치를 이용하기 때문에 새로운 모양이 등장하지 않는다. 그렇기 때문에 1일 때의 경우의 수 + 2일 때의 경우의 수를 하면 N이 3일 때의 경우의 수가 도출된다. 점화식으로는 dp [i] = dp [i-1] + dp [i-2]로 표현할 수가 있다.

 

import java.util.*;

public class Main {
	
	static int dp[];
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		dp = new int[n+1];
		
		dp[1] =1;
		if(n>=2) // 런타임 에러 방지
			dp[2]=2;
		
		for(int i=3;i<=n;i++) {
			dp[i] = dp[i-1]+ dp[i-2];
			dp[i] = dp[i] % 10007; //int타입의 데이터 범위를 벗어나지 않게 나머지값을 저장한다.
		}
		
		System.out.println(dp[n]);
		

		
	}
	
}