1, 2, 3 더하기 4

경우의 수를 세는 문제로, 1, 2, 3 더하기 문제를 풀었다면 지금까지 이런 변형 문제를 풀었던 방식대로 똑같이 풀면 된다.

이 문제에서는 숫자의 순서가 달라도 조합이 같으면 같은 수로 본다.

이런식의 문제는 우리가 적절히 규칙을 추가해주고 갯수를 세면 되는데, 보통 숫자의 조합이 달라도 같은 경우의 수를 세는 문제에서는 숫자를 오름차순으로 놓는 규칙을 정하는게 일반적인 것 같다.

우리 나름대로 숫자를 오름차순으로만 생성한다고 규칙을 정해놓고 답을 구해도, 어쨌든 정답은 같기 때문이다.

이 문제에서 숫자는 오직 1, 2, 3밖에 사용되지 않으므로 숫자를 오름차순으로 정렬하면 모든 숫자는 끝이 1, 2, 3으로 끝나게 된다.

여기까지 생각했다면 나머지는 1, 2, 3 더하기와 똑같이 풀면 되고, 단지 맨 끝에 1, 2, 3으로 끝나는 숫자에 대한 정보만 추가적으로 관리하면 된다.

• dp[n][0]: 숫자 n의 조합중 끝자리가 1인 경우의 수
• dp[n][1]: 끝자리가 2인 경우의 수
• dp[n][2]: 끝자리가 3인 경우의 수

위와 같이 정해놓고 나면, dp[n]을 오름차순을 유지하면서 어떻게 구성해야 되는지 알 수 있을 것이다.

• dp[n][0]은 dp[n-1][0] 뒤에 1만 붙이면 된다.
• dp[n][1]은 dp[n-2][0], dp[n-2][1] 뒤에 2만 붙이면 된다.
• dp[n][2]는 dp[n-3][0], dp[n-3][1], dp[n-3][2] 뒤에 3만 붙이면 된다.

package main

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

var (
    sc *bufio.Scanner
    wr *bufio.Writer
)

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

    wr = bufio.NewWriter(os.Stdout)
}

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

func main() {
    tc := scanInt()

    var dp [10001][3]int

    dp[1][0] = 1

    dp[2][0] = 1
    dp[2][1] = 1

    dp[3][0] = 1
    dp[3][1] = 1
    dp[3][2] = 1

    for n := 4; n <= 10000; n++ {
        dp[n][0] = dp[n-1][0]
        dp[n][1] = dp[n-2][0] + dp[n-2][1]
        dp[n][2] = dp[n-3][0] + dp[n-3][1] + dp[n-3][2]
    }

    for tci := 0; tci < tc; tci++ {
        n := scanInt()
        sum := dp[n][0] + dp[n][1] + dp[n][2]
        wr.WriteString(strconv.Itoa(sum))
        wr.WriteByte('\n')
    }
    wr.Flush()
}