BOJ:移動[15989]

6125 ワード
テキストリンク

1.質問


整数4を1,2,3の和と表す方法は4種類ある.和を表すときは1つ以上の数を使います.構成和の数だけ順序が違うのは同じです.
1+1+1+1
2+1+1 (1+1+2, 1+2+1)
2+2
1+3 (3+1)
整数nが与えられると、nが1、2、3の和で表される方法の数を求めるプログラムが作成される.
出典:https://www.acmicpc.net/problem/15989

2.アイデア

  • 積算値比較
  • 『欲造の数』[1,2,3]

    • 3.コード


    mine
    import sys
n = int(input())

for _ in range(n):

    dp = [[1,0,0],[1,1,0],[1,1,1]]

    a = int(input())
    if a<=3:
        print(sum(dp[a-1]))
        continue
    for i in range(3, a+1):
        tmp = []
        tmp.append(dp[i-1][0])
        tmp.append(dp[i-2][0]+dp[i-2][1])
        tmp.append(dp[i-3][2]+dp[i-3][1]+dp[i-3][0])

        dp.append(tmp)

    print(sum(dp[a-1]))
    フラッタで地図を表示する
    [Tips] Babylon.js でカメラの操作がスマホだと逆方向になってしまう対策