1, 2, 3 더하기 5

1, 2, 3 더하기 시리즈 문제랑 똑같다.

이 문제의 경우, 연속된 두 숫자의 경우는 세지 말라고 조건이 하나 더 붙어있다.

이전 문제에서 경우의 수를 셀 때, 끝자리에 숫자 1, 2, 3을 추가하는 방식으로 숫자를 센다고 했다. 이를 그대로 이용하면 된다.

이 문제의 경우 전체적으로 푸는 방법은 같다. N-1, N-2, N-3을 구성하는 방법의 수를 더하면 되는 것인데, 맨 끝에 어떤 숫자가 있는지 그 정보를 기억하는 것만 추가하면 된다.

이전 문제에서는 모든 경우의 수 정보를 cache[n] 하나로 관리했지만, 이번에는 각 끝자리에 1, 2, 3이 끝나는 수에 대한 정보들을 기억하게 만들면 된다.

답

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func init() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
}

func scanInt() int {
    sc.Scan()
    ret, _ := strconv.Atoi(sc.Text())
    return ret
}

const Mod = 1000000009

func main() {
    // cache[n][0, 1, 2]는 끝에 1, 2, 3으로 끝나는 수
    // cache[n][3]은 cache[n][0, 1, 2]의 합(그냥 코드를 편하게 짜기 위해서 추가함)
    var cache [100001][4]int

    // 초기화
    cache[1][0] = 1
    cache[1][3] = 1

    cache[2][1] = 1
    cache[2][3] = 1

    cache[3][0] = 1
    cache[3][1] = 1
    cache[3][2] = 1
    cache[3][3] = 3

    for n := 4; n <= 100000; n++ {
        for i := 0; i < 3; i++ {
            // n-1, n-2, n-3
            back := n-(i+1)
          
            // 나머지이므로 음수가 되는 경우를 막기 위해 Mod를 더한다.
            cache[n][i] = cache[back][3] - cache[back][i] + Mod
            cache[n][3] += cache[n][i]

            cache[n][i] %= Mod
            cache[n][3] %= Mod
        }
    }

    tc := scanInt()
    for tci := 0; tci < tc; tci++ {
        fmt.Println(cache[scanInt()][3])
    }
}