[알고리즘] SW Expert Acadamy 5215. 햄버거 다이어트

 

 

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

SW Expert Academy

 

import java.util.Scanner;

public class Solution {
	
	static int N;
	static int L;
	static int max;
	
	static int[] arrN;
	static int[] arrL;
	
	static boolean[] check;
	
    public static void main(String[] args) {
    	
    	Scanner sc = new Scanner(System.in);
    	
    	int T = sc.nextInt();
    	
    	for(int t=1; t<=T; t++) {
    		N = sc.nextInt();
    		L = sc.nextInt();
    		
    		arrN = new int[N];
    		arrL = new int[N];
    		check = new boolean[N];
    		
    		for(int i=0; i<N; i++) {
    			arrN[i] = sc.nextInt();
    			arrL[i] = sc.nextInt();
    		}

    		max=0;
    		DFS(0);
    		System.out.println("#" + t + " " + max);
    		
    	}
   }
    
   static void DFS(int cnt) {
	   if(cnt==N) {
		   int sumL = 0;
		   int sumN = 0;
		   for(int i=0; i<check.length; i++) {
			   if(!check[i]) continue;
			   sumL += arrL[i];
			   sumN += arrN[i];
		   }
		   
		   if(sumL > L) return;
		   
		   max = Math.max(max, sumN);
		   
		   return;
		   
	   }
	   check[cnt] = true;
	   DFS(cnt+1);
	   check[cnt] = false;
	   DFS(cnt+1);
   }
   
}

 

 

 

📌 참고할만한 풀이

package algorithm_lab.day03.q1;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

public class Hamburger {
   
   static int N, L,max_score;
   static int[] jumsu,cal;
   public static void main(String[] args) throws NumberFormatException, IOException {
      System.setIn(new FileInputStream("./src/algorithm_lab/day03/q1/sample_input.txt"));
      BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
      
      int test_case=Integer.parseInt(br.readLine());
      
      for(int T=1;T<=test_case;T++) {
         String[] s= br.readLine().split(" ");
         
         N= Integer.parseInt(s[0]);
         L=Integer.parseInt(s[1]);
         jumsu= new int[N];
         cal=new int[N];
         max_score=0;
         
         for(int i=0;i<N;i++) {
            String[] s2=br.readLine().split(" ");
            jumsu[i]=Integer.parseInt(s2[0]);
            cal[i]=Integer.parseInt(s2[1]);
         }
         
         check(0,0,0);
         
         StringBuilder sb=new StringBuilder();
         sb.append("#").append(T).append(" ").append(max_score).append("\n");
         System.out.print(sb.toString());
      }
   }
   
   public static void check(int cnt, int total_score, int total_cal) {
      //기저 조건
      if(total_cal>L) return;
      if(cnt==N) {
         max_score=Math.max(total_score, max_score);
         return;
      }
      
      //해당 재료를 선택 할 때
      check(cnt+1,total_score+jumsu[cnt],total_cal+cal[cnt]);
      // 해당 재료를 선택하지 않을 때
      check(cnt+1,total_score,total_cal);
      
   }
}