[SWEA] 5215. 햄버거 다이어트

5215. 햄버거 다이어트

---

문제 풀이

• 부분 집합을 구하는 powerset(멱집합) 알고리즘을 활용

t = int(input())

for i in range(1, t + 1):

    n, l = map(int, input().split())  # 재료 수, 제한 칼로리
    cal = []
    for _ in range(n):
        # 점수, 칼로리
        cal.append(list(map(int, input().split())))

    # best : 점수는 높지만 칼로리는 낮은 것
    cal = sorted(cal, key=lambda c: c[1])
    total = 0

    def dfs(idx, score, calo):
        global total

        if calo > l:  # 칼로리 합이 l보다 크다면 return
            return

        if idx >= n:    # idx가 n을 넘을 경우, return
            if score > total:  # 맛 점수가(score) 기존 total보다 크다면 score를 넣어준다.
                total = score
            return

        dfs(idx + 1, score + cal[idx][0], calo + cal[idx][1])
        dfs(idx + 1, score, calo)  # 위의 cal[idx][1] + calo > l 이면, return 되어 기존의 score과 calo값을 가진다.

    dfs(0, 0, 0)
    print(f"#{i} {total}")

PowerSet 알고리즘

def powerSet(dta, flag, n):

    if n == len(data):
        for i in range(len(flag)):
            if flag[i] == 1:
                print(data[i], end=' ')
        print()
        return

    flag[n] = 1
    powerSet(data, flag, n + 1)

    flag[n] = 0
    powerSet(dta, flag, n + 1)


if __name__ == '__main__':

    data = ['a', 'b', 'c']
    flag = [0] * (len(data))

    powerSet(data, flag, 0)

출력 결과

a b c 
a b 
a c 
a 
b c 
b 
c 

---

참고 블로그

• PowerSet 알고리즘 코드