[백준] 2xn 타일링 Java

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

11726번: 2×n 타일링

 

 

풀이

 

 

# 2x1

2x1 1개

1가지 경우의 수

 

 

 

# 2x2

2x1 2개

1x2 2개

2가지 경우의 수

 

 

# 2x3

3가지 경우의 수

 

 

# 2x4

5가지 경우의 수

 

......

 

 

점화식

dp[n] = dp[n-2] + dp[n-1] 도출 가능

 

 

 

 

 

    public void solution11726() throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

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

        int dp[] = new int[1001];


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

        for(int i=3; i<=n; i++){
            dp[i] = (dp[i-1]+dp[i-2])%10007;
        }

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

    }

 

여기서 주의할 점 !!

dp 배열 크기를 n+1 로 잡으면 런타임 에러 (ArrayIndexOutOfBounds) 발생하기 때문에

입력의 최대값인 1000 + 1 의 길이로 최대 배열 생성 후 사용