[問題解決]Baek Jun-14226表情(dfs&bfs)

提问链接

問題の説明

英善は喜んでいたので、孝彬にSの微笑みを送りたい.
英善はすでに画面に表情を入力した.現在、S個の表情を作成するには、以下の3つの演算のみを使用します.

画面のすべての表情をクリップボードにコピーして保存します.

クリップボードのすべての表情を画面に貼り付けます.

画面の1つの表情記号を削除します.

すべての演算には1秒かかります.また、表情をクリップボードにコピーすると、以前のクリップボードの内容が上書きされます.クリップボードが空の場合に貼り付けたり、一部をクリップボードにコピーしたりすることはできません.また、クリップボードの一部の表情は削除できません.画面に表情を貼り付けると、クリップボードの表情が画面に追加されます.
1つのプログラムを編纂して、英仙がスクリーンの上でS個の表情を作成するのに要する時間の最大値を求めます.

入力

第1行はS(2≦S≦1000)を与える.

しゅつりょく

S個の表情を作成するのに要する時間の最大値を1行目に出力します.

入力例1

2

サンプル出力1

2

入力例2

4

サンプル出力2

4

入力例3

18

サンプル出力3

8

私の答え

bfsを用いて解決した.
bfsは、まず隣接ノードにアクセスするナビゲーションである.
つまり가까운 정점, 가까운 거리에 있는 노드를 먼저 탐색です.
最低料金、最高価格を探している場合は、多く利用してください.
(ただし、重みは1でなければなりません)
check[display][board]を行うのは,探索した場所を再探索する必要がなく,最高値を求める必要があるためcheckingを行う必要があるためである.
問題の条件のように、点火式に分けて解決した.
display=1,board=0,count=0を初期化します.
ナビゲーション順序

スクリーン表情を回路基板にコピーする=>回路基板が上書きされるので、スクリーン表情数と同じ数を得ることができる.board = display , count+= 1

クリップボードの表情を画面に追加し、+=ボード、count+=1

を表示します.

画面表情-1 display-=1 count+=1

探索が終了するとcountは時間の最高値である.

コード#コード#

from collections import deque

n = int(input())
max_size = 1001
check = [[-1]*max_size for _ in range(max_size)]
def bfs():
    queue = deque()
    queue.append((1, 0, 0))
    
    while queue:
        display, board, count = queue.popleft()
        
        if display == n:
            return count
        
         # 1.화면에서 보드로 저장
        if 0 < display < max_size: 
            if check[display][display] == -1:
                check[display][display] = 1
#                 count += 1
                queue.append((display, display, count+1))
                
        # 2. 보드에서 화면으로 저장, display + board 몽땅 화면에 저장되기 때문에 비교 필요    
        if 0 < board and display + board < max_size : 
            if check[display+board][board] == -1:
                check[display+board][board] = 1
                queue.append((display+board, board, count+1))
        # 3. display에서 하나 삭제
        if check[display-1][board] == -1:
            check[display-1][board] =1
            queue.append((display-1, board, count+1))

print(bfs())