[백준, BOJ 2133] 타일 채우기 (java)

출처-https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

---

내 생각 :

3xn은 맨 아래나 맨 위에 1x2 타일이 꼭 붙어있어야 하므로 n은 반드시 2의 배수여야만 타일을 꽉 채울 수 있다.
우선 n이 2일 때는 다음과 같은 모양의 3개의 패턴이 가능하다.(dp[2]=3)

손으로 그려서 엉망진창인 그림~

또한 N이 2씩 커질때마다 다음과 같은 특수한 패턴이 2개씩 더 생긴다.

손으로 그려서 엉망진창인 그림(2)~

(위 그림은 각각 n이 4, 6, 8일 때 생기는 특수한 패턴들이다.)
매번 생기는 이 2개의 특수한 패턴 때문에 다음의 식이 나온다.
dp[i]=dp[i-2]*dp[2]+dp[i-4]*2+dp[i-6]*2+...+dp[0]*2
우선 dp[i-2]*dp[2]은 dp[i-2]에 3x2 타일인 dp[2]를 덧붙여주는 경우이다.
이 경우 말고도 dp[i-4]에 dp[4]에서 생긴 특수한 패턴의 타일을 덧붙여주어도 d[i] 형식의 타일이 될 수 있다.
따라서 dp[i-4]에 dp[4]에서 생긴 특수한 패턴 2가지를 곱해준다.
마찬가지로 dp[i-6]은 dp[6]에서 생긴 특수한 패턴의 타일 2가지를 곱해주는 형식이 된다.
마지막으로 d[0]를 곱해주는 이유는 d[i]에서 생긴 특수한 패턴 2가지를 더해주기 위함이다.
따라서 위의 식과 같은 형태가 나온다.

 ==>>답은 나오는데 런타임 에러가 뜬다.
 하....
 그래서 dp[i] 구할 때마다 매번 dp[0]*2+dp[2]*2+...+dp[i-4]*2를 해줘서 그런 줄 알고
 mul에 저장해놓고 i+=2 될 때마다
 mul+=dp[i-4]해서 dp[i]+=mul만 하면 되게 했다.
 또 런타임 에러가 뜬다.
 ㅋㅋㅋㅋㅋㅋㅋㅅㅂ
 그래서 잘은 모르겠지만 입력받는 시간부터 출력까지 시간이 런타임인가? 싶어서
 입력 범위가 30까지니 처음부터 dp[30]까지 만들고 입력받아 출력했다.
 드디어 "맞았습니다!!"가 뜬다.
 이렇게 또 하나 알아가네ㅎ

728x90

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scan=new Scanner(System.in);
		int dp[]=new int[31];
		
		dp[0]=1;
		dp[2]=3;
		int mul=0;
		for (int i=4;i<=30;i+=2) {
			dp[i]+=dp[i-2]*dp[2];
			mul+=dp[i-4]*2;
			dp[i]+=mul;
		}
		int n=scan.nextInt();
		System.out.println(dp[n]);
	}

}