[SWEA] 1486. 張勲の高架[D 4]

📚 質問する

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}')     # 차이를 출력

🔍 結果