[백준] 14852번: 타일 채우기 3 - java

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

public class Main {

	static int n;
	static final int MOD = 1000000007;
	static long[][] dp = new long[1000001][2];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		// dp[n]=2* dp[n-1] + 3*dp[n-2]+ (2* dp[n-3]+ 2*dp[n-4] + .... + 2*dp[0] )
		// dp[i][1] => i-3까지의 합 누적 => dp[n-3]+dp[n-4] + ... + dp[0] = dp[i-3][0] +
		// dp[i-1][1]
		// dp[i][0] = 2 * dp[n-1][0] + 3 * dp[n-2][0] + 2 * dp[i][1]
		dp[0][0] = 0;
		dp[1][0] = 2;
		dp[2][0] = 7;
		dp[2][1] = 1; // dp[3][1] = 2이기 때문

		for (int i = 3; i <= n; i++) {
			dp[i][1] = (dp[i - 3][0] + dp[i - 1][1]) % MOD;
			dp[i][0] = (3 * (dp[i - 2][0]) + 2 * (dp[i - 1][0]) + 2 * dp[i][1]) % MOD;
		}
		System.out.println(dp[n][0]);

	}

}

너무너무 어려웠던 문제..
결국 2시간동안 해결하지 못해서 다른 분의 코드를 참고했다.
dp를 이중배열로 사용할 생각은 미처 하지 못했는데,, 이번 문제로 시야가 조금 넓어진 느낌이다.


기존의 타일채우기와 일치하게 dp[i] 점화식을 세운다면, 아래와 같다.

dp[i] = 2*dp[i-1] + 3*dp[i-2];

그러나 이 문제의 경우, 1x1의 타일이 존재하기 때문에 항상 2가지의 예외가 발생한다.
즉, dp[i] 을 구하고 싶다면 2*dp[i-1] + 3*dp[i-2] 뿐만 아니라, dp[i-j] 에 새로 생긴 1x2의 공간으로 인해 더해진 2가지 예외를 곱해줘야 한다.
=> 2 * (dp[n-3] + dp[n-4] + dp[n-5] + ... + 1) 을 추가로 더해준다!!

즉, 점화식을 정리하자면 다음과 같다.

• dp[i][1] => i-3까지의 합 누적 => dp[n-3]+dp[n-4] + ... + dp[0] = dp[i-3][0] + dp[i-1][1]
  • dp[i-1][1] 에는 dp[i-4] 까지의 누적합이 들어있을 것이므로, 여기에 dp[i-3]의 값을 더해줘야 한다.
  • 구한 dp[i] 까지의 누적합을 이용해서 dp[i][0]값을 구할 수 있다.
• dp[i][0] = 2 * dp[n-1][0] + 3 * dp[n-2][0] + 2 * dp[i][1]
  • 2 * dp[n-1][0] + 3 * dp[n-2][0] 
    • (n-1)의 경우의 수 * (1x2개짜리 타일을 놓는 경우의 수 2개) +
    • (n-2)의 경우의 수 * (2x1개와 1x1로 타일을 놓는 경우의 수 3개)
  • 2 * dp[i][1]
    • 예외 2가지를 구하기 위한 i까지의 누적합 
    • => ( dp[i-3][0] + dp[i-4][0] + ... 1 ) * 2( 1x1 타일로 생기는 예외 2가지)

   		dp[0][0] = 0;
		dp[1][0] = 2;
		dp[2][0] = 7;
		dp[2][1] = 1; // dp[3][1] = 2이기 때문

		for (int i = 3; i <= n; i++) {
			dp[i][1] = (dp[i - 3][0] + dp[i - 1][1]) % MOD;
			dp[i][0] = (3 * (dp[i - 2][0]) + 2 * (dp[i - 1][0]) + 2 * dp[i][1]) % MOD;
		}

휴,,,, dp2차원배열.... 쉽지않다