SWEA - 5215. 햄버거 다이어트

햄버거가 먹고싶어서 선택한 문제

 

전체 재료 중 몇가지만 선택해야한다는 제약 조건이 없고, 그냥 제한 칼로리 이하로만 맞추면 된대서

부분집합 알고리즘을 사용해서 풀었다.

 

재귀함수를 돌면서 부분집합 원소 추가 여부를 선택해주고,

전체 재료 수 만큼 다 돌면, 이제 원소로 되어있는 것들끼리 더해서 총 점수가 몇인지 알아보는 것.

 

import java.util.*;

public class Solution {

	public static int T,N,L,sum;
	public static int[] score,cal;
	public static boolean[] visit;
	
	public static void main(String[] args)  {

		Scanner sc = new Scanner(System.in);
		
		T = sc.nextInt();
		
		for (int i = 1; i <= T; i++) {
			sum=0;
			N = sc.nextInt();
			L = sc.nextInt();
			score = new int[N];
			cal = new int[N];
			visit = new boolean[N];
			
			for (int j = 0; j < N; j++) {
				score[j] = sc.nextInt();
				cal[j] = sc.nextInt();
			}
			
			comb(0);
			
			System.out.println("#"+i+" "+sum);
			
		}
		
	}
	
	public static void comb(int idx) {
    
		if(idx==N) {
			int totalScore=0, totalCal=0;
			
			for (int i = 0; i < N; i++) {
				if(visit[i]) { //부분집합 원소 O 인것들만 더하기
					totalScore+=score[i];
					totalCal+=cal[i];
				}
			}
			
            // 제한 칼로리 이하인 것만 score 대소비교
			if(totalCal<=L)
				sum = Math.max(totalScore, sum);
			
		} else {
			//부분집합 ㅇ표시
			visit[idx] = true;
			comb(idx+1);//,totalScore+score[idx],totalCal+cal[idx]);
			
            //부분집합 X표시
			visit[idx] = false;
			comb(idx+1);//,totalScore,totalCal);
		}
	}

}

 

 

+) 코드 리뷰를 통해 더 간단한 코드로 변경

부분집합 원소 체크할 필요없이.. 그냥 선택한건 아싸리 total에 더해주고 아닌건 더하지 않는다.

어짜피 조합은 순서가 중요하지 않으니까!

	public static void comb(int idx,int totalScore, int totalCal) {
		if(idx==N) {
			
			if(totalCal<=L)
				sum = Math.max(totalScore, sum);
			
		} else {
			
			comb(idx+1,totalScore+score[idx],totalCal+cal[idx]);
			
			comb(idx+1,totalScore,totalCal);
		}
	}