SWEA 1486번 D4 장훈이의 높은 선반 파이썬

리뷰

첫 번째 D4 문제 풀이였다. 비트 마스킹 문제는 경험한 적이 없어 그냥 선채로 죽었다. 어려웠다.

문제 풀이

모든 경우의 수를 구한 뒤 선반의 높이와 가장 가까운 값을 도출하고자 했다. 2중 for문을 사용해 제출했으나 정답 맞추기에 실패하였다. 

결국 모든 경우의 수를 찾기 위해 비트마스킹 알고리즘을 사용한다는 것을 접하게 되었고 2 ** n 크기의 경우의 수에서 나올 수 있는 경우의 수를 모두 찾고 각 경우의 수에 선택된 점원의 합이 선반의 높이보다 크거나 같다면 해당 값을 현재 result 값과 비교하여 더 적다면 result를 갱신하도록 했다.

참고 사항

result의 초기값은 n의 최대 범위가 20이고 h의 최대 범위가 10000이므로 200001 이상으로 설정해 주면 된다.

정답 코드

def q1486():
    # SWEA 1486번 D4 장훈이의 높은 선반 파이썬
    t = int(input())
    for i in range(1, t + 1):
        n, b = map(int, input().split())
        lst = list(map(int, input().split()))
        result = 200001
        for j in range(2 ** n):
            temp = 0
            for k in range(n):
                if j & (2 ** k):
                    temp += lst[k]
            if temp >= b:
                result = min(result, temp)
        print(f'#{i} {result - b}')
q1486()