BAEKJOON : 10844, 2193


No. 10844


1. Problem

2. My Solution
  • 長さnの階段数が10種類に分かれている場合
    -ゼロで終わるカウント
    -1で終わる数
    -2で終わる数
    - ...
    -9で終わる数字
  • 2 D配列を使用すると、エンドがどのように終了するかに関する情報を格納することもできます.
  • 隣接する数字の差は1でなければならないので、末尾に大きな数字または小さな数字
  • を1つ追加することができる.
  • 例)長さnのステップ数のうち1で終わる数は、n-1で終わる数に0または2で終わる数を加えた
  • に等しい.
  • セグメントですが、0は1です.  9は8万かもしれませんが、
  • を単独で処理する必要があります.
    import sys
    
    n = int(sys.stdin.readline().rstrip())
    
    dp = [[0]*10 for _ in range(101)]
    dp[1] = [0,1,1,1,1,1,1,1,1,1]
    
    for i in range(2,n+1):
       for j in range(0,10):
            if j == 0:
                dp[i][j] = dp[i-1][j+1] % 1000000000
            elif j == 9:
                dp[i][j] = dp[i-1][j-1] % 1000000000
            else:
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000
    
    print(sum(dp[n]) % 1000000000)

    No. 2193


    1. Problem

    2. My Solution
  • 第1の方法
  • n=1ルールを探し始める->フィボナッチ数の原理
  • import sys
    
    n = int(sys.stdin.readline().rstrip())
    dp = [0]*91
    dp[1] = dp[2] = 1
    
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    
    print(dp[n])
  • 第2の方法
  • nビットこのパラメータは2つの場合に分けられます
    0で終わるこの親水性
    -1で終わるこの親水性
  • 2 D配列を使用すると、エンドがどのように終了するかに関する情報を格納することもできます.
  • は0に終わり0と1を追加でき、1に終わり0を追加できます
    import sys
    
    n = int(sys.stdin.readline().rstrip())
    dp = [[0,0] for _ in range(91)]
    dp[1][1] = 1
    
    for i in range(2,n+1):
        dp[i][0] = dp[i-1][0] + dp[i-1][1]
        dp[i][1] = dp[i-1][0]
    
    print(sum(dp[n]))
    4. Learned
  • アルゴリズムを様々な方法で実装しましょう