백준 11726번: 2xn 타일링

 

public void calculate(int val) {
		int[] dp = new int[val + 1];
		dp[0] = 0;
		if(val>0) {
			dp[1] = 1;
		}
		if(val>1) {
			dp[2] = 2;
		}
		for (int i = 3; i <= val; i++) {
			dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
		}

		System.out.println(dp[val]);
	}

 

간단히 손으로 끄적여보거나 테스트 코드를 작성하여 결과를 도출 해보았다면,

0~9...에서 0, 1, 2, 3, 5, 8, 13 ,21, 34, 55...순으로 값이 증가하는 것을 확인 할 수 있다.

 

위 값을 토대로 점화식을 도출하면

n>2 에서 dp[n] = dp[n-1] + dp[n-2] 를 만족하는 것을 확인 할 수 있다.

 

단, 주의 할 점은 순서대로 계속 더해나가면 어느순간 dp값이 int 나 long 의 범위를 초과하게 된다.

 

0~2 까지 디폴트 값을 선언하고 그 외의 값에 대해서 dp[]에 적재 할 때, 미리 주어진 값으로 나눈 나머지 값을 적재 하도록 하자.