/ SWEA

SWEA_5215_햄버거다이어트_JAVA

문제 : 햄버거다이어트

SWEA문제는 로그인을 해야 열람할 수 있습니다.

링크 : SWEA_5215_햄버거다이어트

접근 방식

햄버거 N개 중에서 X개를 선택하여 칼로리 L이 넘지 않는 선에서 가장 큰 선호도를 얻는 문제이다.

부분집합으로 해결할 수 있는 문제이다.

N개중에 X개를 고르는 문제는 조합, 그 조합의 경우의 수를 nC1부터 nCn까지 따져봐야 하는 문제는 부분집합이다.

풀이 방법 1

재귀함수를 통해 부분집합의 기본을 구현해 푸는 방법과, 인자값을 조금 더 사용해서 처리속도를 조금 더 빠르게 하는 방법 두 가지로 풀어보았다.

  1. 해당 재귀 메서드의 인자값은 cnt 하나 뿐이다.

  2. 부분집합의 구현중, 반복조건은 재귀를 통해 특정 원소가 선택되었을 때와 선택되지 않았을 때를 구분하여 재귀시킨다.

  3. boolean형 배열을 isSelected에 N개만큼 선언하여 선택과 비선택을 구분하도록 한다.

  4. 부분집합 재귀의 기저조건은 cnt를 0부터 증가시켜 N이 되었을 때 멈추도록 한다. 이때, isSelected 배열에 true인 값이 선택된 값이므로, 해당하는 값이 true인 경우에 모든 선호도와 칼로리를 더하도록 한다.

  5. 칼로리와 선호도의 합이 구해졌다면, 칼로리가 주어진 L값과 비교하여 더 작은 경우에만 다음 작업이 진행되도록 한다.

  6. 칼로리가 L보다 작을 경우, 선호도의 합과, 기존 선호도를 비교하여 더 큰 값을 기존 선호도에 저장한다. (MAX값 찾기)

  7. 모든 반복이 종료된 후 Max값이 저장된 기존 선호도를 출력한다.

소스 코드 1

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class D3_5215_햄버거다이어트2 {
	static int cal;
	static int score;
	static int inscore;
	static boolean[] isSelected;
	static int[][] arr;
	static int N, L;
	static int k=1;
	public static void main(String[] args) throws NumberFormatException, IOException {
		System.setIn(new FileInputStream("input_5215.txt"));

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(in.readLine());

		for(int tc = 1; tc <= T ; tc++) {
			String[] str = in.readLine().split(" ");
			N = Integer.parseInt(str[0]);
			L = Integer.parseInt(str[1]);
			arr = new int[N][2];
			isSelected = new boolean[N];
			for(int i=0;i<N;i++) {
				String[] str2 = in.readLine().split(" ");
				for(int j=0;j<2;j++) {
					arr[i][j] = Integer.parseInt(str2[j]);
				}
			}
			score = 0;
			search(0);
			System.out.printf("#%d %d\n", tc, score);
		}
	}

	public static void search(int cnt) {
		if(cnt == N) {
			for(int i=0;i<N;i++) {
				if(isSelected[i]) {
					inscore += arr[i][0];
					cal += arr[i][1];
				}
			}
			if(cal < L) {
				if(score < inscore) {
					score = inscore;
				}
			}
			cal = 0;
			inscore = 0;
			return;
		}


			// 현재 원소를 선택
			isSelected[cnt] = true;
			search(cnt+1);
			// 현재 원소를 비선택
			isSelected[cnt] = false;
			search(cnt+1);
		}

}

풀이 방법 2

  1. 풀이 방법 1과 골자는 비슷하다. 부분집합을 재귀를 통해 구현하는데, 원소가 선택되었을 때, 선택되지 않았을 때를 구분한다.

  2. 인자값을 추가한다. 재귀에서 사용할 인자값으로 횟수를 체크할 cnt, 내부의 선호도라는 뜻의 inscore와 칼로리를 저장할 cal 을 int 타입으로 받는다.

  3. boolean형 배열은 사용하지 않는다.

  4. 반복조건으로, 현재 원소가 선택된 경우, 기존 inscore값 + 현재 선호도, 기존 cal값 + 현재 cal을 추가하여 재귀해준다. 반대로 현재 원소가 선택되지 않았을 경우, 값을 더하지 않고 읽어온 인자값을 그대로 넘겨준다.

  5. 부분집합 재귀의 기저조건은 cal이 L보다 크다면 재귀를 종료한다. 또한, cnt를 0부터 증가시켜 N이 되었을 때도 멈추도록 한다.

  6. cnt를 0부터 증가시켜 N까지 도달했을 경우, 선호도의 합과 기존 선호도를 비교하여 더 큰 값을 기존 선호도에 저장한다. (MAX값 찾기)

  7. 모든 반복이 종료된 후 Max값이 저장된 기존 선호도를 출력한다.

소스 코드 2


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

public class D3_5215_햄버거다이어트 {
	static int score;
	static int[][] arr;
	static int N, L;
	static int k=1;
	public static void main(String[] args) throws NumberFormatException, IOException {
		System.setIn(new FileInputStream("input_5215.txt"));

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(in.readLine());

		for(int tc = 1; tc <= T ; tc++) {
			String[] str = in.readLine().split(" ");
			N = Integer.parseInt(str[0]);
			L = Integer.parseInt(str[1]);
			arr = new int[N][2];

			for(int i=0;i<N;i++) {
				String[] str2 = in.readLine().split(" ");
				for(int j=0;j<2;j++) {
					arr[i][j] = Integer.parseInt(str2[j]);
				}
			}
			search(0,0,0);
			System.out.printf("#%d %d\n", tc, score);
		}
	}

	public static void search(int cnt, int inscore, int cal) {

		if(cal > L) {
			return;
		}

		if(cnt == N) {
			score = Math.max(score, inscore);
			return;
		}

		// 현재 원소를 선택
		search(cnt+1, inscore+arr[cnt][0], cal+arr[cnt][1]);
		// 현재 원소를 비선택
		search(cnt+1, inscore, cal);
	}
}