TIL#31:[Algorithm]Baekjun/DP/Tiling

新年アルゴリズム学習(1.1~7)

3日目

標準的な質問:
2193, 11726, 11727, 2133

DPバゴン+2👩‍💻

DPを学び始める気持ち🐳

私になるまで、私たちは質問して、勉強して、整理します.
▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼
▼焦らないで、満席にさせてください

A)2193号

条件:
この数

はゼロで始まりません.

この親水性では、1は2回連続して現れない.すなわち、11は部分文字列

ではない
パターンの理解:
~0ビット▷0
~1位†1(1)
~2位†1(10)
~3位†2(100、101)
~4位ϲ3(1000、1001、1010)
まずdp=[0, 1, 1, 2, 3]リストを作成できます!

最初の試行(成功):

# append 
n =int(input())
dp=[0, 1, 1, 2, 3]
 
for i in range(5,91):
    dp.append(dp[i-1]+dp[i-2])

print(dp[n])

N(1 ≤ N ≤ 90)に適したfor문+rangeが作成され、dp[i-1]+dp[i-2]モードが組み込まれている.

問題解決チェックリスト

▼タイムアウトしても問題は起こらない
タイムアウト完了コード
▼コード未完成
#コード完了-エラー
▼コード完了-正しい

B)11726号

図案を知るために[6].
次に、パターンについて説明します.
~1位†1
~2位†2
~3位†3
~4位†5
~5位†8dp=[0, 1, 2, 3, 4, 5]リストを作成してから始めましょう!

最初の試行(成功):

memo = {0:0,1:1,2:2}
def num_tile(number : int) -> int:
    if number in memo:
        return memo[number]
    memo[number] = num_tile(number-1) + num_tile(number-2)
    return memo[number]

num = int(input())
print(num_tile(num) % 10007)

ディックシャナリーを運用しました.
**通常のfor i in range():時間、メモリは29836 KB、76 ms…!

問題解決チェックリスト

▼タイムアウトしても問題は起こらない
タイムアウト完了コード
▼コード未完成
#コード完了-エラー
▼コード完了-正しい

C)11727号

dp=[0, 1, 3, 5]を作成し、dp[i-1] + (2*dp[i-2])を図案とした.

最初の試行(成功):

n = int(input())
dp = [0, 1, 3, 5]
 
for i in range(4,n+1):
    dp.append(dp[i-1] + (2*dp[i-2]))
 
print(dp[n] % 10007)

入出力例8は、モードが正しいことを確認する.171出力成功!

問題解決チェックリスト

▼タイムアウトしても問題は起こらない
▼タイムアウト完了コード
▼コード未完成
#コード完了-エラー
#コード完了-正しい

D)2133号

1時間のパターンを探すために、ずっと絵を描いています.

次に、パターンについて説明します.
~1位†0
~2位†3
~3位†0
~4位†11
**単数は0に出力する必要があります

最初の試行(失敗):

n = int(input())
dp = [0 for _ in range(31)]
dp[2] = 3
dp[4] = 11

for i in range(6, n+1, 2):
    dp.append((dp[i-2] * 3) + 2)
print(dp[n])

0が出てきました

ソース:

n = int(input())
dp = [0 for i in range(31)]
dp[2] = 3
for i in range(4, 31, 2):
    dp[i] = dp[2] * dp[i - 2]
    for j in range(4, i, 2):
        dp[i] += 2 * dp[i - j]
    dp[i] += 2
print(dp[n])

ソース-pacific-ocean

6を作ることができる方法は全部で3種類あります。

basic[4] + [2]
前に2479142で見た形状と2479142で見た形状(11 x 3)*3

[2] + new[4]
以前に2479142で見た形状(作成不可能な接続構造を有する)の新しい形状2479142 3*2

と

new[6]
2479142の新しいモデル2

☄️ dp[4] = 33 + 6 + 2 = 41
1番以降に集中...2日忘れたこんな間違いを犯すな!

問題解決チェックリスト

▼タイムアウトしても問題は起こらない
タイムアウト完了コード
▼コード未完成
▼コード完了-エラー
#コード完了-正しい
Reference
https://www.acmicpc.net/
https://pacific-ocean.tistory.com/208
https://suri78.tistory.com/103