[알고리즘] 백준 11727 2×n 타일링 2 -dp- 자바 코틀린

 

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

 

 

 

백준 dp 유형의 2×n 타일링 2 문제를 풀어봤습니다. ㅎㅎ

이전에 풀었던 문제의 연장선 같은 문제였습니다.

youngest-programming.tistory.com/446

[알고리즘] 백준 11726 2xn 타일링 -dp- 자바

 

먼저 그림을 그려봤는데 다음과 같았습니다.  참고로 앞자리가 2xn인데 1xn 으로 썻네요 실수입니다. 봐주십셩 :)

 

 

이때 2x3 타일을 보면 2x1 두개로 이루어진 세로막대기는 모양중복으로 인해 2x1 타일이(세로막대기) 하나만 붙을 수 있다는걸 제외하고 2x2의 타일들에서 양쪽에 2x1 타일인 가로막대기가 양쪽에 붙어서 만들어짐을 볼 수 있습니다.  (색칠한게 2x1의 세로막대기를 붙인겁니다.) 즉 n번째 타일들의 개수는 n-1, n-2 번째 타일들의 조합으로 풀 수 있고 다음과 같은 식이 도출됩니다.

dp[i] = (dp[i - 1] + 2 * dp[i - 2]) 

 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 3;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
        }
        System.out.println(dp[n]);
    }
}

 

[Kotlin]

import java.util.*


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val dp = IntArray(1001)
    dp[1] = 1
    dp[2] = 3
    for (i in 3..n) {
        dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007
    }
    println(dp[n])
}

 

 

github.com/mtjin/algorithm_practice/blob/master/%EB%B0%B1%EC%A4%80%2011727%202%C3%97n%20%ED%83%80%EC%9D%BC%EB%A7%81%202%20-dp-/Main.java

mtjin/algorithm_practice

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!