백준 JAVA 11726번 2xn 타일

문제 링크: https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

▶ 문제

 2xn 직사각형안에 1x2와 2x1 타일을 채운다. 

 

 

▶ 해설

DP 문제로 판단되어 점화식을 세웠다.

2 = 2

3 = 3

4 = 5

5 = 8

....

9 = 55

위 처럼 나오므로 점화식은 DP[N]=DP[N-1]+DP[N-2]로 도출 할 수 있었다.

 

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int n = Integer.parseInt(s);
        int dp[] = new int [n+1];
        dp[1]=1;
        dp[0]=1;
        for(int i=2; i<n+1; i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        System.out.println(dp[n]);
    }
}