BOJ 9095. 1, 2, 3 더하기

BOJ 9095. 1, 2, 3 더하기

풀이

d[n] = 1, 2, 3의 합으로 나타내는 방법의 수 앞부분들은 겹치는 부분들로 memo 해놓고 계속 사용하게 되니
맨 마지막에 올 수 있는 1, 2, 3의 방법의 수만 찾아보면 된다.

d[n] = O + O + O + …. = n 이므로

• (n -1 ) + 1  = n
• (n -2 ) + 2  = n
• (n -3 ) + 3  = n

위와 같이 3개의 방법이 있다.

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

Bottom-Up

import java.util.Scanner;

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

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

Top-Down

import java.util.Scanner;

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

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

    static int go(int i) {
        if (i == 0) return 1; // 0일때 방법은 1개로 침
        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) + go(i - 3);
        return d[i];
    }
}

val d = IntArray(11) { 0 }

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

fun go(i: Int): Int {
    if (i == 0) return 1 // 0일때 방법은 1개로 침
    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) + go(i - 3)
    return d[i]
}

풀이소스

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