백준(BOJ) 11726 : 2×n 타일링 (실버3) / 자바(Java) 풀이

문제

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

3줄 요약

1. 2×n 직사각형을 채우는 방법의 수를 구하기 위해 점화식을 세웁니다.
   • 2×n 직사각형의 가장 오른쪽에 1×2 타일을 세로로 놓는 경우, 나머지 부분은 2×(n-1) 직사각형을 채우는 방법의 수와 같습니다.
   • 2×n 직사각형의 가장 오른쪽에 2×1 타일을 가로로 2개 놓는 경우, 나머지 부분은 2×(n-2) 직사각형을 채우는 방법의 수와 같습니다.
   • 따라서 2×n 직사각형을 채우는 방법의 수는 2×(n-1) 직사각형을 채우는 방법의 수와 2×(n-2) 직사각형을 채우는 방법의 수를 합한 것과 같습니다.
   • 이를 점화식으로 표현하면 memo[i] = memo[i-1] + memo[i-2]가 됩니다.
2. 메모이제이션 기법을 사용하여 이전에 계산된 값을 저장하고 재사용함으로써 중복 계산을 피하고 효율성을 높입니다.
   • memo 배열을 사용하여 각 크기의 직사각형을 채우는 방법의 수를 저장합니다.
   • 점화식을 이용하여 계산할 때, 이미 계산된 값은 memo 배열에서 가져와 사용합니다.
   • 이렇게 함으로써 동일한 크기의 직사각형에 대한 계산을 반복하지 않고, 한 번 계산된 값을 재사용할 수 있습니다.
3. 문제에서 요구하는 대로 결과에 모듈로 연산(% 10007)을 적용하여 출력합니다.
   • 직사각형의 크기 n이 커질수록 채우는 방법의 수는 매우 큰 값이 될 수 있습니다.
   • 모듈로 연산을 적용하여 결과를 10007로 나눈 나머지를 출력함으로써, 매우 큰 수를 다룰 때 발생할 수 있는 오버플로우를 방지합니다.
   • 이는 결과의 정확성에 영향을 주지 않으면서도, 계산 과정에서 발생할 수 있는 문제를 해결합니다.

코드

// package boj11726;

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // 입력 파일에서 데이터 읽기 (테스트용)
        // System.setIn(new FileInputStream("src/input.txt"));
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 2×n 직사각형의 너비 n 입력받기
        int n = Integer.parseInt(br.readLine());
        
        br.close();
        
        // 메모이제이션을 위한 배열 초기화
        int[] memo = new int[1001];
        
        // 초기 값 설정
        memo[0] = 1;
        memo[1] = 1;
        
        // 동적 계획법을 이용하여 2×n 직사각형을 채우는 방법의 수 계산
        for (int i = 2; i <= n; i++) {
            memo[i] = (memo[i - 2] + memo[i - 1]) % 10007;
        }
        
        // 결과 출력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(Integer.toString(memo[n]));
        bw.flush();
        bw.close();
    }
}