[백준] no11727: 2×n 타일링 2

문제

 

Input
채울 길이 N

Output
위의 1*2, 2*1, 2*2 세 가지 모양의 블록을 이용해 N*2의 블록을 채우는 경우의 수를
10007로 나누어 나머지를 출력

조건
1 <= N <= 1000

---

원리

* DP문제

경우의 수는 
1 -> 1
2 -> 3
3 -> 5
4 -> 11
5 -> 21
6 -> 43
7 -> 85
8 -> 171
...
N -> (N-1번째) + (N-2번째)*2

---

풀이방법

N번째 경우의 수
= (N-1번째 경우의 수) + (N-2번째 경우의 수)*2

---

나의 코드

1. Int형 배열 사용 [14428kb, 128ms]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());
    int[] arr = new int[1001];
    arr[1] = 1;
    arr[2] = 3;
    
    // 3번째 부터 시작
    if(N>2) {
        for (int i = 3; i <= N; i++) arr[i] = (arr[i - 1] + (arr[i - 2] * 2))%10007;  // DP 계산
    }
    
    System.out.println(arr[N]);
}

 

2. ArrayList를 사용 [143326kb, 128ms]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());

    List<Integer> list = new ArrayList<>();
    list.add(1); // 0번째는 1가지
    list.add(1); // 1번째는 1가지
    
    for (int i = 2; i <= N; i++) list.add((list.get(i - 1) + (list.get(i - 2) * 2)) % 10007); // DP 계산
    
    System.out.println(list.get(N)); // 출력
}

---

레퍼런스 코드

참고 링크 : https://dev01.tistory.com/70