[BOJ/Java] 11726. 2xn 타일링

[BOJ/Java] 11726. 2xn 타일링

11726번: 2×n 타일링

---

문제 해석

"2xn 타일링" 문제는 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 찾는 문제다. 이 문제는 동적 프로그래밍을 활용하여 풀 수 있다. 크기가 n인 문제를 해결하기 위해, 먼저 n이 1과 2일 때의 해답을 초기값으로 설정하고, n이 3 이상일 때는 점화식 𝑓(𝑛)=𝑓(𝑛−1)+𝑓(𝑛−2)를 사용하여 해를 구한다.

풀이 과정

프로그램은 BufferedReader를 이용해 입력을 받고 BufferedWriter를 이용해 출력한다. dp 배열을 사용하여 각 크기의 직사각형을 채우는 방법의 수를 저장한다. 배열의 인덱스 i에 대해, dp[i]는 2xi 직사각형을 채우는 방법의 수를 나타낸다.

1. 기본 설정: dp[1]은 1, dp[2]는 2로 설정된다. 이는 2x1 타일과 1x2 타일만으로 각각 채울 수 있기 때문이다.
2. 점화식 적용: i가 3 이상일 때, dp[i] = (dp[i - 1] + dp[i - 2]) % 10007을 이용하여 계산한다. 이 점화식은 타일을 채우는 방법의 수가 매우 커질 수 있기 때문에 10007로 나눈 나머지를 저장함으로써 오버플로우를 방지한다.
3. 결과 출력: 계산된 dp[N]을 StringBuilder를 사용해 BufferedWriter로 출력한다.

코드

package edu.ssafy.im.BOJ.Silver.S3.No11726;

import java.io.*;

public class Main {
    private static int N;  // 타일을 놓을 직사각형의 길이 N
    private static int[] dp;  // 각 길이에 대한 타일링 방법의 수를 저장할 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());  // 입력: 직사각형의 길이 N

        dp = new int[N + 1];  // dp 배열 초기화

        for (int i = 1; i <= N; i++) {
            if (i < 3) dp[i] = i;  // 기본 조건: dp[1] = 1, dp[2] = 2
            else dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;  // 점화식을 이용한 계산
        }

        sb.append(dp[N]);  // 결과 저장
        bw.write(sb.toString());  // 출력
        bw.flush();  // 출력 버퍼 비우기
        bw.close();  // 자원 해제
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)이다. dp 배열을 한 번 순회하면서 각 항목을 계산하기 때문에 입력 크기 N에 비례하는 시간이 소요된다.

느낀점

이 문제는 기본적인 동적 프로그래밍 문제 중 하나로, 간단한 점화식을 활용해 해결할 수 있었다. 문제를 풀면서 동적 프로그래밍의 기초를 다시금 확립할 수 있었고, 큰 수를 다룰 때 모듈로 연산의 중요성을 다시 한번 깨달을 수 있었다.