백준 11726 2*n 타일링 java(dp)

문제 출처 : https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

알고리즘 분류

• 다이나믹 프로그래밍

풀이

2*1 크기의 직사각형을 채우는 방법의 수는 1개

2*2 크기의 직사각형을 채우는 방법의 수는 2개

2*3 크기의 직사각형을 채우는 방법의 수는 3개

2*4 크기의 직사각형을 채우는 방법의 수는 5개

2*5 크기의 직사각형을 채우는 방법의 수는 8개

 

2*1부터 2*5까지의 방법의 수만 확인해봐도

피보나치 수열과 같다는 점을 알 수 있다.

 

따라서 점화식은 dp[i] = dp[i-1]+dp[i-2]이고,

방법의 수가 int가 다룰 수 있는 수보다 커지니,

문제에서 제시한대로 10007을 나눈 나머지를 저장한다.

 

java는 기본적으로 배열의 크기를 변수로 생성할 수 있다.

 

코드1

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int dp[] = new int[1001];
    static final int INF = 10007;
    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        dp[1]=1;
        dp[2]=2;

        for(int i=3;i<=n;i++) {
            dp[i]=(dp[i-1]+dp[i-2])%INF;
        }
        System.out.println(dp[n]);        

    }
}

코드2(재귀)

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int dp[];
    static final int INF = 10007;
    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        dp  = new int[n+1];
        dp[0]=1;
        dp[1]=1;

        System.out.println(recur(n));        


    }

    static int recur(int n) {
        if(dp[n]>0)
            return dp[n];
        dp[n] = (recur(n-2) + recur(n-1))%INF;
        return dp[n];
    }
}