[SWEA][백트래킹] 1486. 장훈이의 높은 선반

1486. 장훈이의 높은 선반

SW Expert Academy

 

• 내 풀이
  • 처음에 가지치기 안해서 런타임 에러 발생
  • 백트래킹할때는 탐색 범위 가지치기 꼭 해줄 것
  • 선택한 것들을 리스트로 따로 담아서 체크

#높이 b
# 탑 - 점원 키 합
# b이상 중 최솟값
from collections import deque

def solve(i):
    global b
    global result
    if sum(top)>=b:
        result=min(sum(top),result)
        return

    for idx,h in enumerate(height):
        if idx<i: continue #가지치기가 꼭 필요하다
        if idx in lst: continue
        top.append(h)
        lst.append(idx)
        solve(idx)
        top.pop()
        lst.pop()


if __name__ == '__main__':
    T=int(input())
    for i in range(1, T+1):
        n,b= map(int,input().split())

        height=list(map(int,input().split()))

        top=deque()
        lst=deque()
        result=int(1e9)
        solve(-1)


        print(result)
        result-=b
        print(f'#{i} {result}')

 

• 다른 사람 풀이
  • 합계가 최소치를 넘어가면 return 해버리기 -> 시간 단축
  • DFS 파라미터 값에서 선택 O,X로 백트래킹 가능

def dfs(idx, hsum):
    global result
    #합계가 이미 최소치를 넘어가면 계산안함
    if hsum >= result:
        return
    #마지막 까지 왔다면
    if idx >= N:
        #선반이상이고 최솟값보다 작을때 값갱신
        if hsum >= B:
            result = hsum
        return
    visited[idx] = True
    dfs(idx+1, hsum + height[idx]) #선택
    visited[idx] = False
    dfs(idx+1, hsum) #선택안함
 
 
T = int(input())
for t in range(1, T+1):
    #N = 점원수, B = 선반높이
    N, B = map(int, input().split())
    height = list(map(int, input().split()))
    result = 987654321
    visited = [False] * N
    dfs(0, 0)
    print('#{} {}'.format(t, result - B))