Algorithm, boj, 타일채우기(2133)

풀이

• n이 홀수일때 모두 채울수없다
• n=2 일때 3가지는 고정
• n=4 일때 2+2=4 이므로 2dp[2] + 4dp[0] ; 고정3가지 말고 4개를 한번에 만들수 있는 방법은 2가지
• 문제 해결의 핵심 : 길이가 2씩 늘어날때마다 2가지 경우가 계속 추가되는 것을 반영해줘야 문제를 해결할 수 있다!!!

package org.baekjoon;

import java.util.Scanner;

public class test2133_dp_fillTile {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int[] dp = new int[31];
		dp[0] = 1;
		dp[3] = 3;

		if(num % 2 == 0) {
		for (int i = 2; i <= num; i += 2) {
			dp[i] = dp[i - 2] * 3;
			// 길이가 2씩 늘어날때마다 2가지 경우가 계속 추가되는 것을 반영해줘야 문제를 해결할 수 있다.
			for (int j = 4; j <= i; j += 2) dp[i] += dp[i - j] * 2;
		}
		}
		System.out.println(dp[num]);
	}

}

---

Reference

• 문제보러가기
• 글 풀이

---