[백준(Java)] 11727. 2×n 타일링 2 ( 재귀 + 메모이제이션)

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

예제 입력 

2

 

예제 출력

3

 

내 풀이

마지막 타일 배치	경우의 수 기여
세로 2×1 하나 배치 → n-1 크기 문제	tileWay(n-1)
가로 1×2 두 개 → n-2 크기 문제	tileWay(n-2)
2×2 타일 하나 → n-2 크기 문제	또 tileWay(n-2)
→ 총 2개의 방식이 n-2에 연결	2 * tileWay(n-2)

 

-> tileWay(n) = tileWay(n - 1) + 2 * tileWay(n - 2)

 

이 점화식을 찾아보자 마자, 바로 재귀함수를 사용하여 문제를 작성하였다.

# 순수 재귀 버전

import java.util.Scanner;

class Main {

    // 순수 재귀로 타일 경우의 수 계산 (메모이제이션 없음)
    public static Long tileWay(int n) {
        if (n == 1) return 1L;
        if (n == 2) return 3L;
        return (tileWay(n - 1) + 2 * tileWay(n - 2)) % 10007;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        System.out.println(tileWay(n));

        sc.close();
    }
}

 

위의 코드에서 결과 값은 정상적으로 출력인된다. 하지만, 문제에서 요구하는 속도의 조건을 충족하지 못하였다.

나의 코드는 하나의 tileway(n) 의 값을 구하기 위해 그 이전의 값들을 반복적으로 수 없이 호출하게 된다. 즉, 이미 앞에서 계산하였던 tileway(n-1) 이나 tileway(n-2)을 다시 계산하는 구조이다. 이 문제를 해결하기 위해서 메모이제이션을 추가하였다. 만약 tileway(n-1)이나 tileway(n-2) 의 값을 계산하면서 배열에 그 값을 배열의 [n-1], [n-2] 의 위치에 저장해 두고, 함수에 그 값이 있으면 바로 반화하는 방식을 사용하였다. 이 방법을 사용하면 불필요한 중첩 호출을 피해 속도를 향샹시킬 수 있다.

 

# 재귀 + 메모이제이션

import java.util.Scanner;

class Main {

    static Long[] buffer;

    // 타일이 들어가는 경우의 수
    public static Long tileWay(int n) {
        if (n == 1) return 1L;
        if (n == 2) return 3L;

        if (buffer[n] != null) return buffer[n]; // 이미 버퍼에 계산된 값이 있으면 계산하지 않고, 바로 리턴

        buffer[n] = (tileWay(n - 1) + 2 * tileWay(n - 2)) % 10007;
        return buffer[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        buffer = new Long[n + 1];

        System.out.println(tileWay(n));

        sc.close();
    }
}

결론 및 정리

항목	순수 재귀	재귀 + 메모이제이션
코드 간결성	✅ 매우 간단	❌ 약간 복잡
중복 계산	❌ 많음	✅ 없음
시간 복잡도	❌ O(2^n) → 매우 느림	✅ O(n) → 빠름
메모리 사용	✅ 거의 없음	❌ 배열 사용
실행 가능한 범위	❌ n ≤ 30 정도까지	✅ n ≤ 1,000 이상도 OK
실전 문제 적합	❌ 비효율적	✅ 실용적

 

깃허브 주소

https://github.com/Chaehyunli/BaekJoon/tree/main/%EB%B0%B1%EC%A4%80/Silver/11727.%E2%80%852%C3%97n%E2%80%85%ED%83%80%EC%9D%BC%EB%A7%81%E2%80%852