11726번 : 2*n 타일링

 

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

 

11726번: 2×n 타일링

 

 

 

 

---

 

 

- 문제

 

 

- 예제

 

 

---

 

 

- 코드

 

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

public class p11726 {
    public static void main(String[] args) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[1001]; // 문제 조건 : 1 <= n <= 1000
        
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= n; i++) {
        // 조금만 계산해보면 아래와 같은 피보나치 수열과 같은 방식으로 반복된다는 것을
        // 알 수 있음. 그리고 모듈러 연산을 통해 매번 % 10007을 해준다.
        // 마지막 계산만 % 10007을 해준다면 오버플로가 발생
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
        }

        System.out.print(dp[n]);
    }
}