[백준] 2xn 타일링 JAVA

이 문제는 동적 계획법(DP)을 활용하여 2×n 크기의 직사각형을 1×2와 2×1 타일로 채우는 방법의 수를 구하는 문제입니다.

점화식

n이 1일 때: 2×1 크기의 직사각형을 채우는 방법은 1가지입니다.
n이 2일 때: 2×2 크기의 직사각형을 채우는 방법은 2가지입니다.
n이 3 이상일 때: rect(n) = rect(n-1) + rect(n-2) 입니다.
rect(n-1)은 직사각형의 마지막에 2×1 타일 하나를 추가한 경우입니다.
rect(n-2)는 마지막에 1×2 타일 두 개를 추가한 경우입니다.

메모이제이션이 활용되는 순간은 이미 계산된 값이 저장되어 있을 때입니다. 이를 통해 다시 같은 값이 필요할 때 저장된 값을 불러와 재계산을 하지 않아도 됩니다.

메모이제이션 예시

rect(5)를 계산하려면 rect(4)와 rect(3)이 필요합니다.
rect(4)를 계산하기 위해 다시 rect(3)과 rect(2)를 계산합니다.
rect(3)과 rect(2)가 계산되었으면, 메모이제이션에 저장됩니다.
나중에 rect(3)이 다시 필요할 때, 저장된 값을 바로 사용하여 재귀 호출을 피합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;

// 2×n 타일링 문제
public class Tiling {
    // 메모이제이션을 위한 Map
    public static Map<Integer, Integer> memo = new HashMap<>();

    public static void main(String[] args) throws Exception {
        // 입력을 받기 위한 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 출력을 위한 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // n값 입력
        int n = Integer.parseInt(br.readLine().trim());

        // 결과 계산
        int result = rect(n);

        // 결과 출력
        bw.write((String.valueOf(result)));
        bw.flush();
        bw.close();
        br.close();
    }

    // 재귀를 이용한 타일링 방법 수 계산
    public static int rect(int n) {
        // 기본 조건: n이 1 또는 2일 때
        if(n <= 2) return n;

        // 이미 계산된 값이 있으면 그 값을 반환 (메모이제이션)
        if(memo.containsKey(n)) return memo.get(n);

        // 점화식 적용 및 10007로 나눈 나머지 계산
        int result = (rect(n - 1) + rect(n - 2)) % 10007;

        // 계산된 결과를 메모이제이션에 저장
        memo.put(n, result);

        return result;
    }
}

주요 포인트

재귀와 동적 계획법: 문제를 작은 문제로 나누어 재귀적으로 해결하며, 이를 최적화하기 위해 메모이제이션을 사용했습니다.
메모이제이션: 이미 계산한 값은 다시 계산하지 않고 저장된 값을 바로 반환합니다. 이를 통해 불필요한 계산을 줄일 수 있으며 성능을 크게 향상시킬 수 있습니다.
모듈러 연산: 결과값이 커질 수 있기 때문에, 중간 계산마다 10007로 나눈 나머지를 계산하여 결과값을 출력합니다.