BOJ 14852 타일채우기 3 풀이

와.. 문제를 푸는데 2시간이 걸렸다.

코드에 변화가 2번이 일어났는데, 처음에는 subproblem을 너무 쉽게 생각했고,

그 다음에는 반복문 내용을 수정했다..

풀이 방법은

위에 1x2랑 1x1로 채우고 밑에를 n-1로 해줘서 d[n-1] * 2

그리고 2x1, 1x1로 채우고 밑에를 n-2로 채워서 d[n-2] * 3

그리고 1x2, 2x1, 1x1을 전부 사용해 위에를 채운건 d2[n-1]+d[n-3] * 2

합치면 d[n-1]*2+d[n-2]*3+(d2[n-1]+d[n-3])*2

	import java.io.*;
	import java.util.*;
	/**
	* BOJ 14852 타일채우기 3
	* https://gist.github.com/KSH-code/aaf918ce45a1ca3da9705f4a83aae78b
	*/
	public class Main{
	private static final int MOD = (int)(1e+9)+7;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int N = Integer.parseInt(br.readLine());
	long dp[] = new long[N+10];
	long dp2[] = new long[N+10];
	dp[1]=2;
	dp[2]=7;
	dp[3]=22;
	dp2[3]=1;
	for(int i = 4; i<=N; i++){
	dp2[i] = (dp2[i-1]+dp[i-3])%MOD;
	dp[i] = (dp[i-2]*3+dp[i-1]*2+dp2[i]*2)%MOD;
	}
	System.out.println(dp[N]);
	}
	}

view raw Main.java hosted with ❤ by GitHub