세 줄로 타일 깔기 (정올 2112)

문제링크

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1374&sca=99&sfl=wr_subject&stx=%EC%84%B8%EC%A4%84 

JUNGOL

풀이

점화식

d[2] = 3

d[4] = d[2]*3 + 2

d[6] = d[4]*3 + d[2] * 2 + 2

d[8] = d[6] * 3 + d[4]* 2 + d[2] * 2 + 2

코드

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		int[] dp=new int[n+1];
		dp[2]=3;
		for(int i=4;i<=n;i+=2) {
			dp[i]+=dp[i-2]*3;
			for(int j=i-4;j>=2;j-=2) {
				dp[i]+=dp[j]*2;
			}
			dp[i]+=2;
		}
		System.out.println(dp[n]);
	}
}

참고

https://jaeyoon8783.tistory.com/m/79?category=873882 

[DP] 3열 타일 채우기 + pro문제 타일 채우기