(Baekjoon) dp - (1) 2×n 타일링

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

fibonacci 수열을 구할때랑 똑같다.

 

2xn의 직사각형에서

 

n==1 일때는 2x1을 넣는 경우의수 총 1개

n==2 일때는 2x1로 채우는 방법한개, 1x2로 채우는 방방법한개 , 총 2개

n==3 일때는..

.....

....

...

..

.

 

n=x 일경우 경우의수는?

 

여기서 모든 경우의수를 차근차근 고려하는것은 내가 아닌 컴퓨터가 계산한다고 치고

마지막에 들어올 경우의수부터 따져보자.

 

여기까지는 강의에서 나온것을 토대로 쓴것이고

사실상 저렇게 직관적으로 생각하는것은 매우 어렵다고 생각한다. 

 

dp문제에서 핵심은 규칙성을 찾는것이다. 그러한 규칙성은 점화식으로 표현되어야 하며

점화식을 dp로 표현하여 푸는것이 문제의 핵심이다.

 

 

package dp;

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

public class _11726{
    
    static int d[] = new int[1001];
    public static int dp(int x){
        if(x == 1) return 1;
        if(x == 2) return 2; 
        if(d[x] != 0) return d[x];
        return d[x] = (dp(x-2) + dp(x-1)) % 10007;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println(dp(Integer.parseInt(br.readLine())));
    }

}

 

 

 

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study