[Java]백준 11726번 2Xn 타일링(Dynamic Programming)

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

풀이

---

2 x n 직사각형을 2x1 과 1x2 사이즈의 타일로 채우는 방법의 경우의 수를 찾는 문제이다

   

1. n = 1일 경우 2x1 타일 한개 배치

2. n = 2일 경우 2x1 타일 2개 or 1x2 타일 2개 배치 

3. n = 3일경우 n =1 일 경우와 n = 2 일 경우의 타일 배치 이용하여 새로운 모양 등장 x

 => n이 3일 경우 -> n이 1일 경우 + n이 2일 경우

  ∴ dp[i] = dp[i-1] + dp[i-2]

 

 

public class algo_11726_dp {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int 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;  //
		}
		
		System.out.println(dp[n]);
	}

}