BOJ 11726 2×n 타일링

By kuper0201

Published in 알고리즘

2023-05-25

1 min read

문제

입력

풀이

문제

BOJ 11726 2×n 타일링 바로 가기

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

풀이

해당 문제는 2×N 크기의 직사각형을 1×2, 2×1 크기의 타일들로 채우는 방법의 수를 구하는 문제이다.

이 문제는 DP(Dynamic Programming)를 활용하여 해결 할 수 있다. N=1일 경우부터 N=3인 경우까지를 각각 그림으로 살펴보자.

먼저 N=1인 경우를 생각해 보면 1×2 타일 하나로 직사각형을 채울 수 있으므로 방법의 수는 1이다. 이를 그림으로 나타내면 다음과 같다.

다음으로 N=2인 경우에는 1×2 타일을 2개 사용하거나 2×1 타일 2개 사용하여 직사각형을 채울 수 있으므로 방법의 수는 2이다.

마지막으로 N=3인 경우를 살펴 보면 N=2인 직사각형에 1×2 타일 하나를 추가하는 경우와 N=1인 직사각형에 2×1 타일 2개를 추가하는 경우를 고려할 수 있다. 그림으로 나타내면 다음과 같다.

이러한 규칙을 점화식으로 나타내면 다음과 같다.

dp[N] = dp[N-1] + dp[N-2]

해당 점화식이 맞는지 확인하기 위해서 N=1부터 N=5까지의 개수를 손수 구해보면 다음과 같다.

1, 2, 3, 5, 8

구한 수열에서도 점화식이 성립하는 것을 알 수 있다. 피보나치 수열과 같은 결과라는 것 또한 알 수 있다.

따라서 찾아낸 점화식을 코드로 구현하면 해당 문제를 해결 할 수 있다.

코드 보기(Java)

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[N + 2];

        // 첫 항 설정
        dp[1] = 1;

        // 점화식에 따라 dp배열 업데이트
        for(int i = 2; i <= N + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] %= 10007;
        }

        // 정답 출력
        System.out.print(dp[N + 1]);
    }
}

코드 보기(C++)

#include <iostream>
#include <cstring>

#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define endl '\n'

using namespace std;

int main() {
    fastio;
    
    // 가로 길이 입력
    int N;
    cin >> N;
    int dp[N + 2];
    memset(dp, 0, sizeof(dp));

    // 첫 항 설정
    dp[1] = 1;

    // 점화식에 따라 dp배열 업데이트
    for(int i = 2; i <= N + 1; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
        dp[i] %= 10007;
    }

    // 정답 출력
    cout << dp[N + 1] << endl;
    
    return 0;
}

코드 보기(Kotlin)

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    // 가로 길이 입력
    var N = readLine().toInt()
    var dp = Array<Int>(N + 2, {0})

    // 첫 항 설정
    dp[1] = 1

    // 점화식에 따라 dp배열 업데이트
    for (i in 2 .. N + 1) {
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= 10007
    }

    // 정답 출력
    println(dp[N + 1])
}

코드 보기(Python)

from sys import stdin

def main():
    # 가로 길이 입력
    N = int(stdin.readline())
    dp = [0] * (N + 2)

    # 첫 항 설정
    dp[1] = 1

    # 점화식에 따라 dp배열 업데이트
    for i in range(2, N + 2):
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] = dp[i] % 10007

    # 정답 출력
    print(dp[N + 1])

if __name__ == "__main__":
    main()

코드 보기(Swift)

import Foundation

func main() {
    // 가로 길이 입력
    var N = Int(readLine()!)!
    var dp = [Int](repeating: 0, count: N + 2)

    // 첫 항 설정
    dp[1] = 1

    // 점화식에 따라 dp배열 업데이트
    for i in 2..<N + 2 {
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= 10007
    }

    // 정답 출력
    print(dp[N + 1])
}

main()