[SWEA] 1486. 張勲の高架[D 4]
5961 ワード
📚 質問する
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE&problemTitle=1486&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1
一人一人を選ぶことができて、選ばないで、選ばないで.だから組み合わせです.
時間の複雑さを減らすために枝を切ります.
まず,再帰的に決定したcur,キーの和を関数のパラメータとして利用する.
ex). 5名の場合、curは0から1名の順に確認し、4に確認し、5から終了する.
選ぶと身長の和が増え、選ばないとcur 1だけ増える.
curが5人だった瞬間は全員を確認した瞬間だった.このとき、身長の和がタワーの高さに等しいかどうかを確認します.
大きいか同じか、結果に入れます.resultは、タワーの高さ以上の数の中で最小の数です.
したがって,解法中にキーの和がresultより大きい場合は直ちに終了する.
📒 コード#コード#
def recur(cur, total): # 조합
global result
if result <= total: # result보다 현재 합이 더 크면 종료
return
if cur == n: # 모든 인원을 확인했으면
if total >= top: # top보다 크거나 같은지 확인
result = min(result, total) # result보다 작은지 확인
return
recur(cur + 1, total) # 현재 사람을 고르는 경우
recur(cur + 1, total + arr[cur]) # 고르지 않는 경우
t = int(input())
for tc in range(1, t+1):
n, top = map(int, input().split())
arr = list(map(int, input().split()))
result = 10000 * n # 키가 최대 10000
recur(0, 0) # 조합으로 확인
print(f'#{tc} {result - top}') # 차이를 출력🔍 結果
Reference
この問題について([SWEA] 1486. 張勲の高架[D 4]), 我々は、より多くの情報をここで見つけました https://velog.io/@yunhlim/SWEA-1486.-장훈이의-높은-선반-D4テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol