[BOJ 2133] 타일 채우기 (Java)

https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

import java.util.Scanner;

public class Main {
	static int N;
	static int[] dp;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		dp=new int[N+1];
		if (N>1) {
			dp[2]=3;
		}
		if (N>=4 && N%2==0) {
			dp[N]=func(N);
		}
		System.out.println(dp[N]);

	}
	private static int func(int n) {
		if (n<4 || dp[n]!=0) return dp[n];
		int sum=3*(func(n-2));
		for (int i=4; i<=n-2; i+=2) {
			sum+=(func(n-i)*2);
		}
		dp[n]=sum+2;
		return dp[n];
	}

}

타일의 가로 길이가 N개일때(a(n))=> (N-2)개는 채워져있고 2개를 채워야 할 경우 (3*(a(n-2))) <2개를 채우는 경우는 3가지>

=>(N-4)개는 채워져있고 4개를 채워야 할 경우 (2*(a(n-4))) 가지 ...

=>(N-6)개는 채워져있고 6개를 채워야 할 경우 (2*(a(n-6))) 가지 ...

=>(N-8)개는 채워져있고 8개를 채워야 할 경우 (2*(a(n-8))) 가지 ...

 

이런 식이 도출된다는 것을 알 수 있다.

 

조금 구현이 복잡한데 다른 분(https://kosaf04pyh.tistory.com/236)의 코드를 보니,

dp[31]까지 다 만든 뒤 반복문을 이용해 for문을 4~n까지 돌려줘서 채워주면 된다..재귀로 할 필요 없다.