BOJ 11726. 2xn 타일링

BOJ 11726. 2xn 타일링

풀이

d[n] = 2*n 크기의 직사각형을 채우는 방법의 수 앞부분들은 겹치는 부분들로 memo 해놓고 계속 사용하게 되니

점화식
d[n] = d[n-1] + d[n-2]

또한 d가 1일 때 방법은 1개이므로, d[1] = 1

d가 2일 때 방법은 1개이므로, d[2] = 2

Bottom-Up

import java.util.Scanner;

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

fun main() {
    val n = readLine()!!.toInt()
    val d = IntArray(n + 1) { 0 }
    d[1] = 1
    d[2] = 2
    for (i in 3..n) d[i] = (d[i - 1] + d[i - 2]) % 10007
    println(d[n])
}

Top-Down

import java.util.Scanner;

class Main {
    static int[] d = new int[1001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(go(sc.nextInt()));
    }

    static int go(int i) {
        if (i == 1) return 1;
        if (i == 2) return 2;
        if (d[i] > 0) return d[i];
        d[i] = (go(i - 1) + go(i - 2)) % 10007;
        return d[i];
    }
}

val d = IntArray(1001) { 0 }

fun main() {
    println(go(readLine()!!.toInt()))
}

fun go(i: Int): Int {
    if (i == 1) return 1
    if (i == 2) return 2
    if (d[i] > 0) return d[i]
    d[i] = (go(i - 1) + go(i - 2)) % 10007
    return d[i]
}

풀이소스

github.com/beomjo/algorithm-study/blob/main/BOJ/java/11726.java github.com/beomjo/algorithm-study/blob/main/BOJ/kotlin/11726.kt