[BOJ]15650-NとM(2)
3483 ワード
展開
1からNまでの数字の中から、M個の数列を選択して昇順で出力します.
まず、復帰で解決できると思います.そして、久しぶりにDFSを実装してから、やっと意識不明の時に実行するコードを書くことができました(…).
backtracking問題がまだ解決されていないためかDFSと何が違うのか疑問に思っていたので少し理解しました.実施から見ると事実上は同じだが,解題策を策定する際には観点が異なるようだ.オーストラリアみたいな感じかな?
に近づく
1からNまでの数字の中から、M個の数列を選択して昇順で出力します.
まず、復帰で解決できると思います.そして、久しぶりにDFSを実装してから、やっと意識不明の時に実行するコードを書くことができました(…).
コード#コード#
from sys import stdin
N, M = tuple(int(i) for i in stdin.readline().split())
def search(answer, depth, next_idx):
global N, M
if depth == M:
print(" ".join(answer))
return
for i in range(next_idx, N + 1):
answer += str(i)
search(answer, depth + 1, i + 1)
answer.pop()
search([], 0, 1)
一般的なDFSで使用されるアクセスの有無配列は、この問題では書く必要はありません.元のデータはアルファベット順に並べ替えられているため,次のナビゲーション範囲を調整するだけで繰返しナビゲーションを防止できるといえる.backtracking問題がまだ解決されていないためかDFSと何が違うのか疑問に思っていたので少し理解しました.実施から見ると事実上は同じだが,解題策を策定する際には観点が異なるようだ.オーストラリアみたいな感じかな?
Reference
この問題について([BOJ]15650-NとM(2)), 我々は、より多くの情報をここで見つけました https://velog.io/@gmelan/BOJ-15650-N과-M2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol