beomjo

beomjo

beomjo dev log 🧑‍💻

BOJ 15990. 1, 2, 3 더하기 5

2 minute read

BOJ 15990. 1, 2, 3 더하기 5

image

풀이

d[n] =  n을 1, 2, 3으로 나타내는 방법의 수 (두 번 이상 연속 X) 

마지막으로 오는 수가 1이면? 그 앞에 올 수 있는 숫자는 2 또는 3이 된다.
마지막으로 오는 수가 2이면? 그 앞에 올 수 있는 숫자는 1 또는 3이 된다.
마지막으로 오는 수가 3이면? 그 앞에 올 수 있는 숫자는 1 또는 2이 된다.

마지막이 1로 끝낫을경우, 2로 끝났을 경우, 3으로 끝났을 경우를 찾아서 2차원 배열에 저장해보자

d[i][j] 1로 끝났을경우 2로 끝났을 경우 3으로 끝낫을 경우
1 1 X X
2 X 1 X
3 1 1 1
4 2 X 1

점화식
d[i][1] = d[i-1][2] + d[i-1][3]  //i 가 1로 끝났을 경우
d[i][2] = d[i-2][1] + d[i-2][3] //i 가 2로 끝났을 경우
d[i][3] = d[i-3][1] + d[i-2][2] //i 가 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 maxValue = 100_001;
        long[][] d = new long[maxValue][4];
        long mod = 1_000_000_009L;

        d[1][1] = d[2][2] = d[3][3] = d[3][1] = d[3][2] = 1;

        for (int i = 4; i < maxValue; i++) {
            d[i][1] = (d[i - 1][2] + d[i - 1][3]) % mod;
            d[i][2] = (d[i - 2][1] + d[i - 2][3]) % mod;
            d[i][3] = (d[i - 3][1] + d[i - 3][2]) % mod;
        }

        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println((d[n][1] + d[n][2] + d[n][3]) % mod);
        }
    }
}

fun main() {
    val maxValue = 100_001
    val d = Array(maxValue) { LongArray(4) { 0 } }
    val mod = 1_000_000_009L

    d[1] = longArrayOf(0, 1, 0, 0)
    d[2] = longArrayOf(0, 0, 1, 0)
    d[3] = longArrayOf(0, 1, 1, 1)

    for (i in 4 until maxValue) {
        d[i][1] = (d[i - 1][2] + d[i - 1][3]) % mod
        d[i][2] = (d[i - 2][1] + d[i - 2][3]) % mod
        d[i][3] = (d[i - 3][1] + d[i - 3][2]) % mod
    }

    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        println((d[n][1] + d[n][2] + d[n][3]) % mod)
    }
}

Top-Down

import java.util.Scanner;

class Main {
    static long[][] d = new long[100_001][4];
    static long mod = 1_000_000_009L;

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

        d[1][1] = d[2][2] = d[3][3] = d[3][1] = d[3][2] = 1;

        while (t-- > 0) {
            int i = sc.nextInt();
            System.out.println((go(i, 1) + go(i, 2) + go(i, 3)) % mod);
        }
        sc.close();
    }

    static long go(int i, int num) {
        if (i <= 3 || d[i][num] != 0) {
            return d[i][num];
        }

        d[i][1] = (go(i - 1, 2) + go(i - 1, 3)) % mod;
        d[i][2] = (go(i - 2, 1) + go(i - 2, 3)) % mod;
        d[i][3] = (go(i - 3, 1) + go(i - 3, 2)) % mod;

        return d[i][num] % mod;
    }
}

val d = Array(100_001) { LongArray(4) { 0 } }
const val mod = 1_000_000_009L

fun main() {
    d[1] = longArrayOf(0, 1, 0, 0)
    d[2] = longArrayOf(0, 0, 1, 0)
    d[3] = longArrayOf(0, 1, 1, 1)


    repeat(readLine()!!.toInt()) {
        val i = readLine()!!.toInt()
        println((go(i, 1) + go(i, 2) + go(i, 3)) % mod)
    }
}

fun go(i: Int, num: Int): Long {
    if (i <= 3 || d[i][num] > 0) {
        return d[i][num]
    }

    d[i][2] = (go(i - 2, 1) + go(i - 2, 3)) % mod
    d[i][1] = (go(i - 1, 2) + go(i - 1, 3)) % mod
    d[i][3] = (go(i - 3, 1) + go(i - 3, 2)) % mod

    return d[i][num] % mod
}

풀이소스

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

You May Also Enjoy