[伯俊]9095号:1.2.3加号問題

2548 ワード
beakjoon 白駿 銀色。 テキストリンク
質問リンク
https://www.acmicpc.net/problem/9095
解き方
  • 整数4の数字は7(1+2+4)、5の数字は13(2+4+7)です.
    • 従って、整数Nの個数は(N−3)+(N−2)+(N−1)の和であり、以下のような点火式を確立することができる.
    てんかしき
    dp[n] = dp[n-3] + dp[n-2] + dp[n-1]
    or
    dp[n] = sum(dp[i-3:i])
    完全なコード
    T = int(input())
for _ in range(T):
    N = int(input())
    dp = [1, 2, 4]
    for i in range(3, N):
        dp.append(sum(dp[i-3:i]))
    print(dp[N-1])
    AWS配備後の感想
    [プログラマー]不良ユーザー