백준 11726 자바 - 2*n 타일링

문제

---

 

 

문제해결

---

 

- 1*2와 2*1의 직사각형으로 2*n을 만들 수 있는 경우의 수는 1, 2, 3, 5, 8....

 

- 2*3의 직사각형을 만들기 위해선

모든 2*2 직사각형에(dp[i-1]) 세로 타일 하나 추가 한 경우의 수

+

모든 2*1 직사각형에(dp[i-2]) 가로 타일 두개 추가한 경우의 수

즉 dp[i] = dp[i-1] + dp[i-2]

- 2*0을 제외하고 보면 피보나치 수열임을 알수있다 

- 2*0일 경우를 임의로 1로 설정하면 피보나치 수열 해결 방식으로 문제 풀이가 가능하다

- 피보나치 수열의 경우 n이 증가함에 따라 값이 기하급수적으로 커지므로 10007이라는 값을 항상 나눠줘서 overflow가 안나게 한다

import java.util.Scanner;
//피보나치 수열
public class B11726 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //dp 배열의 크기는 n+1
        int[] dp = new int[n+1];
        //0,1 은 1로 초기화
        dp[0] = 1;
        dp[1] = 1;
        //2부터 dp[i] = dp[i-1] + dp[i-2]로 dp 배열 채우기
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
            dp[i] %= 10007;//int에 담을 수 있게 10007로 나머지 연산 수행하는듯
        }
        //dp 배열의 n번째 수가 최대 만들 수 있는 횟수
        System.out.println(dp[n]);
    }
}