[JAVA, C++] 백준 11726번 2xn 타일링 문제 - DP 알고리즘

DP알고리즘의 또 다른 문제 2xn타일 구하기 문제이다.

이 문제도 어제 풀었던 1, 2, 3 더하기와 똑같은 원리로 이루어져 있다.

우선, 타일은 2x1 과 1x2 이 두가지가 주어진다.

그러다면 우리가 바로 알 수 있는 경우의 수는 1일떄와 2일때이다.

tile[1] 일때, 2x1 하나밖에 쓰이지 못하니 경우의 수는 1이다.

또, tile[2] 일때, 2x1 타일을 두개 겹친 것과 1x2 타일을 가로로 두 개 겹친 것해서 경우의 수는 2가지가 나온다.

그렇다면 3일때는 어떨까?

2x1타일을 앞에 세울 때, 2가지 경우와 1x2타일을 두개로 겹쳐서 2x2로 만들때 1가지 경우의 수를 더하면 3가지의 경우의 가지가 나온다.

그렇다. 2x1타일을 맨 앞에 세웠을 때의 경우의 수와 1x2타일을 가로로 겹쳐 2x2로 만드는 경우의 수 두가지를 생각하면 된다!

백준 예시에서 나오는 tile[9]일때,

2x1타일을 맨 앞에 세웠을 때 남은 타일의 개수는 2x8이다. 

1x2타일을 가로로 두개 겹쳐 2x2타일을 맨 앞으로 세웠을 때 남은 타일의 개수는 2x7이다.

이런식으로 생각해서 일반화를 하다 보면 tile[i] = tile[i - 1] + tile[i-2]가 된다.

이제 이걸 코딩하면 된다.

이번에도 역시 bottom-up방식으로 하였다.

재귀를 사용하는 top-down은 아직 내게 많이 어려운 부분인 것 같다. ㅠㅠ

 

* C++

#include <iostream>
using namespace std;

int d[1001];
int main() {
	d[0] = 1;
	d[1] = 1;
	int n;
	cin >> n;
	for (int i = 2; i <= n; i++) {
		d[i] = d[i - 1] + d[i - 2];
        d[i] %= 10007;
	}
	cout << d[n];
	return 0;
}

 

* JAVA

import java.util.*;

public class Beak_11726 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		
		int[] tile = new int[1001];
		
		tile[0] = 0;
		tile[1] = 1;
		tile[2] = 2;
		
		for(int i = 3; i <= num; i++) {
			tile[i] = (tile[i - 1] + tile[i - 2]) % 10007;
		}
		System.out.println(tile[num]);
		sc.close();
	}

}