[Java] 백준 2133번 : 타일 채우기

1. 문제

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

2133번: 타일 채우기

 

 

 

2. 풀이과정

채운다 = 빈칸없게!

1) n이 0이나 홀수면, 0을 출력

2) 짝수면 아래의 규칙을 따름

p[n] = (p[n-2]*3) + (p[n-4]*2) + (p[n-6]*2) + ... = (p[n-2]*3) + (p[n-4] + p[n-6] + ... )*2

 

2칸일 때, 가능한 건 3가지, 4칸일 때만 가능한 건 2가지, 6칸일 때만 가능한 건 2가지, ... , 그 뒤로 모두 2가지씩 있다.

여기서 6칸일 때만 가능하다는 말은 n=2, n=4일 때처럼 6보다 작은 타일에서 블럭을 어떻게 더해도 나올 수 없지만, n=6에 속하는 경우들을 말한다. 아래 그림에서는 옅은 색으로 표시하였다.

 

식을 글로 풀어보면, n-2에서 바로 2칸을 추가해서 n을 가는 경우 + n-4에서 바로 4칸을 추가해서 n으로 가는 경우 + n-6에서 바로 6칸을 추가해서 n으로 가는 경우 ... 라고 볼 수 있다.

 

주의할 점은, "바로"라는 점이다. 2칸+2칸으로 이루어진 4칸을 가는 건 바로 가는 경우가 아니다. 옅은 색으로 표시한 것이 바로 n으로 갈 수 있는 블럭들을 의미한다.

 

 

import java.util.Scanner;

public class Boj2133 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		if(n==0 || n%2==1)
			System.out.println(0);
		else {
			int arr[] = new int[n+1];
			arr[2] = 3;
			int cnt = 1;//바로 가는 경우의 수*2
			for(int i=4;i<=n;i+=2) {
				arr[i] = arr[i-2]*3+cnt*2;
				cnt+=arr[i-2];
			}
			System.out.println(arr[n]);
		}
	}
}