[Algorithm] - 백준 11727 2xn 타일링 2 - Java

2번도 마찬가지로 메모이제이션을 이용!

규칙을 찾아서 배열로 해결하는 문제~

package backjoon;

/*문제

2×n 크기의 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.*/

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class back11727 {

public static void main(String[] args) throws Exception{

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int n = Integer.parseInt(br.readLine());

int tile[] = new int[1001];

tile[1] = 1;

tile[2] = 3;

for(int i=3; i<=n; i++){

tile[i] = (tile[i-1] + tile[i-2]*2) % 10007;

}

System.out.println(tile[n]);

}

}