[SWEA] [부분집합] [백트래킹] 5215. 햄버거 다이어트

5215. 햄버거 다이어트

SW Expert Academy

 

• 파이썬 풀이
  • 백트래킹
  • kcal가 limit을 넘어갈때만 처리하니까 테케가 전부다 통과하지 못함 -> 반례가 있을듯 
    • => limit을 넘어가면 return 하고, 작거나 같은 모든 상황을 비교하면서 max 값 구해줌
  • limt보다 작거나 같은 상황에 result값을 갱신하면서 return 해버리면 안됨!
    • 작은 값일때는 그 값을 이용해서 더 돌아가야하기 때문에 return 되면안됨

    # if kcal >=limit:
    #     if kcal>limit:
    #         score-=lst[idx-1][0]
    #         kcal-=lst[idx-1][1]
    #     result=max(result, score)
    #     return
    
   => 조건문 이걸로 하면 error

# 칼로리 이하 조합 중 가장 높은 점수
def make(score, kcal,idx):
    global limit
    global result
    
    if kcal>limit: return
    result=max(result,score) #작은값일때는 리턴하면안됨

    for i in range(idx, len(lst)):
        s,k=lst[i]
        score+=s
        kcal+=k
        make(score,kcal,i+1)
        score-=s
        kcal-=k


T=int(input())

for tc in range(1,T+1):
    n,limit=map(int,input().split())

    lst=[]
    result=0
    for i in range(n):
        s,k=map(int,input().split())
        lst.append((s,k))

    lst.sort(key=lambda x:x[1])
    make(0,0,0)

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

 

• 자바 풀이 - powerset

class Solution
{
	static int N, L, maxScore; //재료 수 , 칼로리 수
    static int[][] lst;

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T= Integer.parseInt(br.readLine());

        for (int test_case=1; test_case<=T; test_case++){
            st= new StringTokenizer(br.readLine());
            N= Integer.parseInt(st.nextToken());
            L= Integer.parseInt(st.nextToken());

            lst= new int[N][2];
            for (int i = 0; i < N; i++) {
                st= new StringTokenizer(br.readLine());
                lst[i][0]=Integer.parseInt(st.nextToken());
                lst[i][1]=Integer.parseInt(st.nextToken());
            }

            maxScore=0;
            select(0,0,0);

            System.out.printf("#%d %d",test_case, maxScore);
            System.out.println();
        }

    }

    public static void select(int idx, int score, int kcal) {
        //칼로리가 넘으면
        if(kcal>L) return;
        //넘지않으면 점수가 높은 값
        if(kcal<=L) maxScore=Math.max(maxScore, score);
        //재료를 다 선택하면
        if (idx==N) return;

        //선택하고 넘기는 경우
        select(idx+1, score+lst[idx][0], kcal+lst[idx][1]);
        //선택하지 않고 넘기는 경우
        select(idx+1, score, kcal);
    }
}