[백준 11727, Java] 2×n 타일링 2

문제

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

풀이

- 2 X n 타일링 문제와 비슷하다

- F(N) 을 구할때 F(N-1) + F(N-2)에서 F(N-2) 즉 2*(N-2)의 직사각형을 구하는 방법은 마지막에 2*2타일을 채우는 방법, 1*2 타일로 채우는 방법 2가지가 있으므로 F(N) = F(N-1) + F(N-2) *2가 된다

[백준 11726, Java] 2 Xn 타일링

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static int[] tileCount;
    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine().trim());
        tileCount = new int[N+1];
        tileCount[0] =1;
        tileCount[1] = 1;

        makeTileBottomUp(N);
        bw.write(String.valueOf(tileCount[N]));
        bw.flush();
        br.close();
        bw.close();


    }
    public static void makeTileBottomUp(int N){
        for(int n = 2; n<=N ; n++ ){
            tileCount[n] = (tileCount[n-1] + 2*tileCount[n-2]) %10007;
        }
    }
}