[SW Expert Academy, SWEA 5215] 햄버거 다이어트 (python)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

---

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

728x90

---

내 생각

완전탐색으로 풀었다.

 

우선, 재료의 맛에 대한 점수, 칼로리를 ingredient 배열에 다음과 같이 담는다.

ingredient = [(100, 200), (300, 500), (250, 300), (500, 1000), (400, 400)]

 

그리고 가능한 모든 조합에 대한 누적 점수와 칼로리를 담을 2차원 배열을 준비한다.

result [[ ], [ ], [ ], [ ], [ ]]

 

우선 ingredient[0]에 대한 가능한 조합을 result[0] 넣는다.

아직 1개의 재료에 대한 조합이니 가능한 조합은 1가지이다.

result = [

[(100, 200)],

[ ],

[ ],

[ ],

[ ]]

 

다음으로 ingredient[1]에 대한 가능한 조합을 result[1]에 넣는다.

가능한 조합은 ingredient[1]만 사용한 조합, ingredient[0] + ingredient[1]인 조합이다.

이는 result[1]에 ingredient[1]을 우선 넣고, result[0]의 조합 중 가능한 것을 result[0][i] + ingredient[1]하면 된다.

이 과정을 하면 result는 다음과 같이 된다.

result = [

[(100, 200)],

[(300, 500), (400, 700)],

[ ],

[ ],

[ ]]

 

result[2]는 result[0][i] + ingredient[2]의 조합, result[1][i] + ingredient[2]의 조합이 있을 것이다.

i = 2:

result = [

[(100, 200)],

[(300, 500), (400, 700)],

[(250, 300), (350, 500), (550, 800), (650), (1000)],

[ ],

[ ]]

 

result[3]는 result[0][i] + ingredient[3]의 조합, result[1][i] + ingredient[3]의 조합,  result[2][i] + ingredient[3]의 조합이 있을 것이다.

하지만 result[3]은 ingredient[3]만으로도 l 이상이 되어버려 다른 조합이 불가능하다.

i = 3:

result = [

[(100, 200)],

[(300, 500), (400, 700)],

[(250, 300), (350, 500), (550, 800), (650), (1000)],

[(500, 1000)],

[ ]]

 

i = 4:

result = [

[(100, 200)],

[(300, 500), (400, 700)],

[(250, 300), (350, 500), (550, 800), (650), (1000)],

[(500, 1000)],

[(400, 400), (500, 600), (700, 900), (650, 700), (750, 900)]]

이다.

 

result[4][0]은 ingredient[4]

result[4][1]은 result[0][0] + ingredient[4],

result[4][2]는 reuslt[1][0] +  ingredient[4],

result[4][3]는 reuslt[2][0] +  ingredient[4],

result[4][4]는 reuslt[2][1] +  ingredient[4]인 것이다.

 

이와 같은 알고리즘으로 코드를 짜주면 된다.

# test case 개수 t
t = int(input())

for test_case in range(1, t + 1):
    # 재료의 수 n, 제한 칼로리 l
    n, l = map(int, input().split())
    
    # 재료의 맛에 대한 점수, 칼로리
    ingredient = []
    for _ in range(n):
        score, cal = map(int, input().split())
        ingredient.append((score, cal))

    # 누적 점수와 칼로리를 담을 배열
    result = [[] for _ in range(n)]

    # 다른 재료들과의 조합 중,
    # 칼로리가 l을 넘지 않는 모든 조합을 result에 저장
    for i in range(n):
        result[i].append(ingredient[i])
        for j in range(0, i):
            for k in result[j]:
                score, cal = k
                if cal + ingredient[i][1] <= l:
                    result[i].append((score + ingredient[i][0], cal + ingredient[i][1]))   

    # 가장 큰 score 구하기
    max_score = 0
    for i in range(n):
        for j in result[i]:
            score, cal = j
            if score > max_score:
                max_score = score

    print("#{} {}".format(test_case, max_score))