[DP] 백준 실버3 11726, 11727번 2xn 타일링, 2xn타일링2

문제

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

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

정답

11726번 정답은 더보기

package BOJ.DP.이곱하기n타일링_11726.insub2004_241110;

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

public class Main {
    // 점화식
    // 규칙이 있었다.
    // d(n) = d(n-2) + d(n-1)

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

        int[] array = new int[n+1];
        array[1] = 1;
        if (n > 1) {
            array[2] = 2;  // n이 1보다 클 때만 array[2] 초기화 (ArrayIndexOutOfBounds)
        }

        for (int i = 3; i <= n; i++) {
            array[i] = (array[i-2] + array[i-1]) % 10007;   // int형의 최대 범위를 벗어날 수 있기 때문에 마지막에 모듈러 연산을 하는게 아니라
        }                                                   // 매 단계마다 모듈러 연산을 해줘야한다.

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

    }
}

11727번 정답은 더보기

package BOJ.DP.이곱하기n타일링2_11727.insub2004_241110;

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

public class Main {

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

        int[] array = new int[n+1];
        array[1] = 1;
        if (n > 1) {
            array[2] = 3;   // (ArrayIndexOutOfBounds)
        }

        for (int i = 3; i <= n; i++) {  // n까지 반복
            array[i] = (array[i-1] + array[i-2]*2) % 10007;
        }

        System.out.println(array[n]);
    }
}

풀이

•  

 

결론

-