1, 2, 3 더하기 3

경우의 수를 푸는 잘 알려진 문제다.

사용할 수 있는 숫자가 1, 2, 3 밖에 없다. 따라서, 어떤 수 N(N > 3)을 구성할 때

• N-1을 구성할 수 있는 모든 수에 1만 덧붙이면 된다.
• N-2를 구성할 수 있는 모든 수에 2만 덧붙이면 된다.
• N-3을 구성할 수 있는 모든 수에 3만 덧붙이면 된다.

즉, cache[n]을 n을 구성할 수 있는 경우의 수라고 한다면 단순히 n-1 n-2 n-3의 경우의 수를 더하기만 하면 된다.

답

package main

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

var sc *bufio.Scanner

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

const mod = 1000000009

func main() {
	var cache [1000001]int
	
	cache[0] = 1
	cache[1] = 1
	cache[2] = 2
	cache[3] = 4

	for n := 4; n <= 1000000; n++ {
		cache[n] = cache[n-1]%mod + cache[n-2]%mod + cache[n-3]%mod
		cache[n] %= mod
	}

	tc := scanInt()

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

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