SWEA) 5215 .햄버거 다이어트(복습 필요)

[입력]
 

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
 

각 테스트 케이스의 첫 번째 줄에는 재료의 수, 제한 칼로리를 나타내는 N, L(1 ≤ N ≤ 20, 1 ≤ L ≤ 104)가 공백으로 구분되어 주어진다.
 

다음 N개의 줄에는 재료에 대한 민기의 맛에 대한 점수와 칼로리를 나타내는 Ti, Ki(1 ≤ Ti ≤ 103, 1 ≤ Ki ≤ 103)가 공백으로 구분되어 주어진다.
 

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 주어진 제한 칼로리 이하의 조합중에서 가장 맛에 대한 점수가 높은 햄버거의 점수를 출력한다.

 

 

[실패 풀이]

생각으로 했을대 각 재료들의 합 들 중 제한 칼로리 안의 조합 중 가장 높음 점수에 해당 되는 값을 출력

값들을 menus에 저장 후 그 값들을 이제 순차적으로 더해 주는 부분 작성 만하면 코드가 끝나나 어떻게 순열로 만들지 머리가 복잡해져서 코드를 완성하지 못하게되었다.

T = int(input())
for number in range(1, T+1):
    # 재료의 수, 제한 칼로
    counts, kal = map(int, input().split())
    menus = []
    for i in range(counts):
      score, sub_kal = map(int, input().split())
      menus.append((score, sub_kal))

    total_score = 0
    for check in range(counts):
        stack = [menus[check]]
        k = (check % counts) + 1
        target_score, target_kal = map(int, menus[check])
        #완전 탐색
        while stack:
            k %= counts
            check_score, check_kal = map(int, menus[k])
            if check == k:
                stack.pop()
                continue

            if check_kal + target_kal > kal:
                k += 1
                continue

            stack.append(menus[k])

 

 

[튜터 풀이]

해당 문제는 재귀 또는 DP로 푸는 문제

 

[튜터풀이 참조 후 DP로 재구현]

이부분에서 핵심은 일단 모든 칼로리를 일단 선언 하고 해당 칼로리에 점수를 등록하는 방식이다

이를 통하여 결국 중복 없이 제한 된 칼로리 안에 넣을 수 있는 모든 가짓 수의 합들이 등록이 되어 있어 그중 큰 값을 불러내면 해당 문제는 간단히 해결이 된다.

T = int(input())
for number in range(1, T+1):
    # 재료의 수, 제한 칼로
    counts, kal = map(int, input().split())
    menus = []
    for i in range(counts):
      score, sub_kal = map(int, input().split())
      menus.append((score, sub_kal))

    dp = [0] * (kal + 1)
    for score, sb_kal in menus:
        for cal in range(kal, sb_kal, -1):
 			dp[cal] = max(dp[cal], dp[cal - sb_kal] + score)
                
    print(max(dp))

 

[튜터풀이 참조 후 재귀로 재구현]

재귀로 구현 했을때 문제는 이게 어떻게 하면 끝이 나는지 확인이 과정이 오래 걸렸다.

일단 먼저 칼로리가 오버되면 점수가 증가하면 안되기에 점수 갱신 위에 종료문이 들어가야 했으며 재료가 모두 소진 됬을때에도 종료를 하기는 해야 하는데 그전에 점수 갱신이 먼저 이루어 져야 해서 재료 소진 전에 점수 갱신이 들어가게 되었다.

이렇게 점수에 관한 부분이 좀 걸렸으며 다음 이제 현재의 값을 넣는 부분을 넣고 재귀를 돌리기 시작

첫번째 재귀는 역시 해당 재료를 사용하는 경우 이며 다음 재귀는 현재의 재료를 사용하지 않는 부분이다.

문제에서 원하는 건 모든 재료를 제한 칼로리안에서 넣는 것이므로 완전 탐색과 비슷하게 모든 가짓수를 생각해야 한다.

그러니 일단 그부분을 사용한 경우와 사용하지 않는 게 들어야 맞기에 이중으로 재귀를 사용한것

 

이 문제를 이해하는 것도 오래 걸렸으며 푸는데는 더 오래 걸렸다. 혼자의 힘으로 푼다고 하였으면 못 풀었는데 튜터님의 친절한 설명으로 문제를 파악하고 어떤걸 이용해야하는지 잘 알 수 있었다.

 

 

이 문제는 시간이 조금 지나고 다시 한번 도전 해야 할 거 같다. 아직은 내가 푼게 아닌거 같으며 비슷한 문제가 주어졌을 때 아직 활용을 못할 거 같다.

def score_find(index, score, kal):
    global max_score
    if kal > K:
        return

    if max_score < score:
        max_score = score

    if index == counts:
        return

    check_score, check_kal = map(int, menus[index])

    score_find(index + 1, score + check_score, kal + check_kal)
    score_find(index + 1, score, kal)

T = int(input())
for number in range(1, T+1):
    # 재료의 수, 제한 칼로
    counts, K = map(int, input().split())
    menus = [list(map(int, input().split())) for _ in range(counts)]

    max_score = 0
    score_find(0,0,0)

    print(f'#{number} {max_score}')