[JAVA] 백준 11726 DP

 

 

 

11726번: 2×n 타일링

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

풀이

이 문제는 DP 문제로 주어진 직사각형 크기를 가득 채우는 방법의 수를 물어본다.

따라서 작은 크기의 사각형부터 하나씩 방법들을 작성하면서 어떤 규칙이 있는지 생각해보고 점화식을 만들었다.

n = 1, 일때 방법은 1가지

n = 2, 일때 방법은 2가지

n = 3, 일때 방법은 3가지

n = 4, 일때 방법은 5가지

n = 5, 일때 방법은 8가지

위의 결과를 보고 유추해보다가 D[n] = D[n-1] + D[n-2]를 성립한다는 것을 깨달았다.

📌 DP 배열 초기화

        long[] A = new long[N];
        for(int i=1; i<N && i < 3; i++){
            A[i] = i;
        }

• 입력값 N이 1일 경우를 대비하여 for문을 사용했다.
• N = 1, N = 2일 경우의 값을 미리 넣어둔다.

📌 DP 배열 만들기

        for(int i=3; i<N; i++){
            A[i] = (A[i-1] + A[i-2] ) % divide;
        }

• 위에서 만든 점화식을 이용하여 DP 배열을 만들어준다.
• 문제에서 10,007로 나눈 나머지 값을 출력하라고 했기 때문에 모든 연산에 나머지 연산을 추가해 오버플로를 방지하였다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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

        int N = Integer.parseInt(br.readLine())+1;
        int divide = 10_007;

        long[] A = new long[N];
        for(int i=1; i<N && i < 3; i++){
            A[i] = i;
        }
        for(int i=3; i<N; i++){
            A[i] = (A[i-1] + A[i-2] ) % divide;
        }
        System.out.println(A[N-1]);
    }

}

결과