[Baekjoon] 11727번 2×n 타일링 2

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

 

설명 :

다이나믹 프로그래밍에의 기본 문제중에 기본 문제인 타일링 문제이다.

특정 모양의 타일들로 직사각형을 채울 수 있는 가짓수를 구한다.

 

다이나믹 프로그래밍을 할 때 가장 중요한 것은 memoization 과 점화식(순환식)이다.

순환식을 먼저 만들어보자.

f(n) 이라는 가상의 함수가 있는데,

이 함수는 2xn 크기의 직사각형을, 주어진 타일들의 개수로 채우는 가짓수를 반환한다.

문제에서 주어진 타일은 2x1, 2x2 두 개의 타일이다.

이 두 개의 타일로 2xn 마지막을 채우는 상상을 해보자.

 

 

위 그림의 설명대로 총 3가지 방법으로 마지막 타일이 채워지게 될 것이다.

그렇다면 아래와 같은 식을 하나 만들 수 있겠다.

 

f(n) = f(n-1) // 2x1 타일 하나로 채우는 경우. 1칸을 채웠음으로 남은 n-1 칸을 채우는 가짓수를 구하면 됨         +f(n-2) // 2x2 타일 하나로 채우는 경우. 2칸을 채웠음으로 남은 n-2 칸을 채우는 가짓수를 구하면 됨.         +f(n-2) // 2x1 타일 둘로 채우는 경우. 2칸을 채웠음으로 남은 n-2 칸을 채우는 가짓수를 구하면 됨.

 

 

정리하면

 

f(n) = f(n-1) + 2*f(n-2)

 

가 된다. 이것이 이 문제의 점화식 되시겠다.

 

이 점화식이 계속 실행된다면 처음에 어떻게 채우느냐가 또 관건이 되는데,

그건 base case 로 우리가 직접 정해줘야 한다.

 

즉,

f(0) 은 방법이 없으므로 f(0) = 0

f(1) 은 2x1 타일 하나로 채우는 경우 밖에 없으므로 f(1) = 1

f(2) 는 2x1 타일 두 개로 채우는 방법이 둘, 2x2 타일 하나로 채우는 방법이 하나, 총 세 가지가 있으므로 f(2) = 3

 

이 base case 를 염두해두고 코드를 작성하면 된다.

 

memoization 을 위해 n 크기만큼의 array 하나를 준비한 다음,

bottom up 방식을 좇아 i=1 부터 i=n 이 될 때까지 차근차근 위의 식 대로 올라가면 된다.

 

마지막에 반환하는 값은, 우리가 알고싶은 "2xn 크기의 직사각형을, 주어진 타일들의 개수로 채우는 가짓수" 이므로

f(n) 을 반환한다.

 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		
		int m[] = new int[n+1];
		for(int i=1; i<=n; i++){
			if(i<2) m[i]=i;
			else if(i==2) m[i]=3;
			else m[i]=m[i-1]+2*m[i-2];
			m[i]%=10007;
		}
		System.out.println(m[n]);
        
    }
}

 

코드 : http://boj.kr/5fcb93cdaa174a98b5d00bc322dc8c5c

 

 

p.s

어떻게 식만 세우고 1부터 차근차근 올라간 것이 우리가 원하는 값이 되는가?

재귀식을 이용한 다이나믹 프로그래밍을 생각해보면,

결국에 재귀식 자체도 똑같은 식을 사용한다고 할 때

가장 아래서부터 하나씩 값을 반환해가면서 순차적으로 n을 향해 쌓여가는 과정을 거친다.

똑같은 식을 그냥 다르게 표현한 거라고 생각하자.

 

bottom up 방식이란, 작은 문제들을 미리 풀어두고

작은 문제들의 결과를 바탕으로 더 큰 문제들을 풀어나가는 것을 말 함

그래서 재귀 함수 대신 반복문을 사용함

 

내가 수강한 다이나믹 프로그래밍 강의

권오흠 교수님 수업 https://youtu.be/K15qLnKKrow