[알고리즘 문제 풀이🙄] 1486. 장훈이의 높은 선반

Gogumiing 2024. 9. 6. 17:25

📌 문제 요약

장훈이가 운영하는 서점에는 높이가 B인 선반이 있다. 서점에 N명의 직원이 일하고 있을 때, 선반에 물건을 올리기 위해 직원들이 탑을 쌓아 올라가려 한다. 각 점원의 키가 배열로 주어질 때, 높이가 B 이상인 탑 중에서 가장 높이가 낮은 탑의 높이를 출력하라.

10개의 테스트 케이스
1 <= N <= 20
각 점원의 키(H)는 1 <= H <= 10,000 의 범위에 속한다.
실행 시간은 Python 4초, Java 2초이다.

🤔 내가 생각한 로직

조합(combination) + 백트래킹
백트래킹을 활용해 유효성 검증을 사용
- [시간복잡도 체크] 내가 생각한 로직이 문제에서 주어진 4가지 조건을 만족하는 로직일까?

😥 틀린 코드와 문제점

# 조합
def combination(empty, target):
    global min_diff
    
    if sum(empty) >= target:
        min_diff = min(min_diff, sum(empty) - target)
        return
    
    for i in range(N):
        if not used[i]:
            used[i] = True
            combination(empty+[heights[i]], target)
            used[i] = False


T = int(input())

for tc in range(1, T + 1):
    # N: 직원 수, B: 선반 높이
    N, B = map(int, input().split())
    heights = list(map(int, input().split()))       # 직원들의 키

    min_diff = 10000 * 20
    used = [False] * N

    permutation([], B)

    print(f'#{tc} {min_diff}')

▶ " Error Message:Memory error occured, (e.g. segmentation error, memory limit Exceed, stack overflow,... etc)" 발생함

🤗 제출 후 pass한 코드

def recur(sum_h, cnt):
    global min_diff
    # 기저조건 가지치기1
    # 탑의 높이가 선반의 높이와 같거나 높아졌는가
    if sum_h >= B:
        min_diff = min(min_diff, sum_h - B)
        return
    
    # 기저조건 가지치기2
    # 모든 직원에 대해 검사했는가
    if cnt == N:
        return
    
    # 현재 직원 포함시킴
    recur(sum_h + heights[cnt], cnt + 1)
    # 현재 직원 포함 안 시킴
    recur(sum_h, cnt + 1)
    

T = int(input())

for tc in range(1, T + 1):
    # N: 직원 수, B: 선반 높이
    N, B = map(int, input().split())
    heights = list(map(int, input().split()))       # 직원들의 키

    min_diff = 10000 * 20
    used = [False] * N

    recur(0, 0)

    print(f'#{tc} {min_diff}')

🧐 참고할 코드

def recur(cnt, sum_height):
    global ans
    # 기저조건 가지치기. 이미 탑의 높이가 B 이상이라면, 더 이상 확인할 필요가 X
    if sum_height >= B:
        # B 이상인 탑 중 가장 낮은 것이 정답!
        ans = min(ans, sum_height)
        return

    # 기저조건. 모든 점원을 탑을 쌓는데 고려했는가 ?
    if cnt == N:
        return

    # cnt 번 점원을 탑에 쌓는다
    recur(cnt + 1, sum_height + heights[cnt])
    # 안쌓는다
    recur(cnt + 1, sum_height)


T = int(input())

for tc in range(1, T + 1):
    N, B = map(int, input().split())
    heights = list(map(int, input().split()))  # 각 점원의 키
    ans = 1e9  # 점원들을 쌓은 탑 중 B 에 가장 가까운 높이를 저장
    recur(0, 0)
    print(f'#{tc} {ans - B}')

▷내 코드는 참고 코드와 기저조건1은 동일하게 주었으나, 모든 직원에 대해 담았다가 뺐다가 하는 과정을 실행하다보니 시간이 초과된 것 같다. 참고 코드처럼 해당 직원을 포함하지 않더라도 탐색했음을 표현하여 모든 직원을 고려했다면 함수를 종료시키는 방향으로 설계했다면 터지지 않았을 것 같단 생각이 든다.

또한 나는 empty라는 빈 리스트를 매번 sum() 함수를 통해 모든 원소들의 합을 구하여 target과 비교했는데, 이또한 시간이 많이 소요된 요소인 것 같다.

▷ 그동안 백트래킹(backtracking)이 가지치기(prunning)라는 것을 알면서도 실제로 가지치기가 어떻게 이루어지는 것인지 감이 잘 오지 않았다. 그런데 이번 문제를 통해 기저조건으로 가지치기를 하는 것을 보고 어떤 것을 '가지치기를 통한 유효성 검사'라고 하는 것인지를 알게 되었다.

😎 앞으로의 개선 방향

지금까지는 특정한 주제로 문제를 풀어왔어서 그날 그날 주제에 맞게 해결 방법을 생각해내면 됐는데, 이제는 모든 기본 알고리즘 학습을 마치고 어떤 알고리즘을 적용할지 직접 생각해내야 하는 상황이 되었다. 그런데 아직 경험이 많지 않아서인지 문제를 봤을 때 어떤 방식으로 접근해야 할지 감이 안 온다. 약간 알쏭달쏭하달까. 뭔가 이렇게 하면 될 것 같고, 또 저렇게 해도 될 것만 같은 느낌이 든다. 우선은 많은 문제를 빠른 시간 내에 접해보면서 그 감을 잡아보려고 노력해봐야 할 것 같다.