[SWEA 코딩] 장훈이의 높은 선반 - PYTHON #1486

소스 코드

def check(temp_sum, idx):
    global res
    
    # n == idx는 끝까지 확인했다는 뜻
    # height의 index는 n-1이 끝이기 때문
    if n != idx:

        # 현재까지의 합이 선반의 높이보다 작은 경우
        if temp_sum < b:
            check(temp_sum,idx+1)
            check(temp_sum+height[idx],idx+1)

        # 그 외의 경우
        else:
            
            # 현재까지의 최소 값보다 현재까지의 합이 작은 경우
            if temp_sum < res:
                res = temp_sum
                return

    # 끝까지 확인한 경우
    else:
        
        # 현재까지의 최소 값보다 현재까지의 합이 작은 경우
        if b <= temp_sum < res:
            res = temp_sum
            return

    return


T = int(input())

for tc in range(1,1+T):

    # 점원의 수, 선반의 높이
    n,b = map(int,input().split())

    # 점원들의 키
    height = list(map(int,input().split()))

    # 결과 저장
    res = 2000000

    # 지금까지의 합, 현재 idx 값
    check(0,0)

    print('#{} {}'.format(tc,res-b))

 

---

해결 방법

1. 조합 문제라 판단하고 접근

 

2. n의 최대값은 20, 직원의 높이를 이용할지 말지를 선택(2가지 선택지) => 최악의 경우의 수는 2^20 => 완전탐색 + 가지치기로 해결

 

3. 탈출 조건은 1) 마지막 직원까지 확인한 경우(index == n인 경우), 2) 현재까지의 합이 선반의 높이보다 큰 경우

 

4. 해당 위치(index)의 직원의 높이를 더할지 말지를 결정해야 함

=> check(현재까지의 직원들의 높이의 합+현재 위치(index)의 직원의 높이, index+1) 더한 경우,

check(현재까지의 직원들의 높이의 합, index+1) 더하지 않은 경우로 나눠서 재귀 호출

---

느낀 점

처음에 return을 사용하지 않아서 깊이 오류가 났는데... 이런 실수를 하지말자 ㅠㅠ

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.