BOJ 2193. 이친수

BOJ 2193.  이친수

풀이

마지막으로 오는 수가 0 일 때 그 앞에 올 수 있는 수는 0,1이다.
마지막으로 오는 수가 1 일 때 그 앞에 올 수 있는 수는 0이다.

점화식
d[i][0] = d[i-1][0] + d[i-1][1]
d[i][1] = d[i-1][0]

Bottom-Up

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

        long[][] d = new long[n + 1][2];

        d[1][1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 1; j++) {
                if (j == 0) d[i][j] = d[i - 1][0] + d[i - 1][1];
                else d[i][j] = d[i - 1][0];
            }
        }
        System.out.println(d[n][0] + d[n][1]);
    }
}

fun main() {
   val n = readLine()!!.toInt()
   val d = Array(n + 1) { LongArray(2) }
   d[1][1] = 1

   for (i in 2..n) {
       for (j in 0..1) {
           d[i][j] = if (j == 0) d[i - 1][0] + d[i - 1][1] else d[i - 1][0]
       }
   }

   println(d[n][0] + d[n][1])
}

Top-Down

import java.util.Scanner;

class Main {
    static long[][] d = new long[91][2];

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

    static long go(int i, int j) {
        if (i == 1 && j == 1) return 1;
        if (i == 1 && j == 0) return 0;
        if (d[i][j] > 0) return d[i][j];

        if (j == 0) {
            d[i][j] = go(i - 1, 0) + go(i - 1, 1);
        } else {
            d[i][j] = go(i - 1, 0);
        }

        return d[i][j];
    }
}

val d = Array(91) { LongArray(2) }

fun main() {
    val n = readLine()!!.toInt()
    println(go(n, 0) + go(n, 1))
}

fun go(i: Int, j: Int): Long {
    if (i == 1 && j == 1) return 1
    if (i == 1 && j == 0) return 0
    if (d[i][j] > 0) return d[i][j]

    d[i][j] = if (j == 0) go(i - 1, 0) + go(i - 1, 1) else go(i - 1, 0)

    return d[i][j]
}

풀이소스

github.com/beomjo/algorithm-study/commit/221467a4207833969f3527a5586429820482d6d9