[백준] 11726번_2xn 타일링(Java)

문제 풀이

백준의 11726번 문제입니다. 문제 출처

(1) 문제 파악

(2) 문제 풀이 방법 생각하기

다이나믹 프로그래밍을 통해 문제를 해결해봅시다!

직사각형을 구성할 수 있는 경우는 두 가지가 있습니다.

• 가장 오른쪽에 1x2 타일을 놓는 경우
• 가장 오른쪽에 2x1 타일을 놓는 경우

그러므로 아래와 같은 점화식을 도출할 수 있습니다.

\[dp[n] = dp[n-1] + do[n-2]\]

주의할 점은 이렇게 계속 더해가면 값이 너무 커지기 때문에 10_007로 나눈 값 자체를 dp 배열에 저장해서 사용해야 합니다!

(3) 시간 복잡도 확인

시간 제한은 1초 입니다. 즉, 대략 1억번 연산 안에 문제를 해결해야 합니다.

\[1 <= N <= 1,000\]

1000까지의 값을 모두 계산하고 원하는 N의 값을 출력하면 되기 때문에 연산 횟수는 1,000회로 문제 해결이 가능합니다!

(4) 구현

import java.io.*;

public class Main {
    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];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        
        for(int i=3; i<1001; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 10_007;
        }

        System.out.println(dp[N]);
        
        br.close();
    }
}