[SWEA] JAVA - 9229. 한빈이와 Spot Mart

재귀 연습을 위해 재귀함수를 사용하여 풀었습니다ㅎㅎ

 

각각 다른 과자 두봉지를 살때 얻을수있는 최대 무게 합을 구하는 문제입니다.

 

우선 solve 함수에서 변화하는 값들을 파라미터로 설정했습니다. idx는 현재 뽑으려는 과자의 인덱스 번호입니다. cnt는 현재까지 뽑은 과자의 개수, weight 는 현재까지 뽑은 과자 무게의 총 합입니다.

 

제가 정의한 solve 재귀 함수의 역할은 idx번째 과자까지 뽑든 안뽑든 지나쳐왔으며 현재까지 뽑은 과자의 개수를 담고있고, 현재까지 뽑은 과자의 무게를 가지고 있습니다.

 

재귀 함수의 동작 방식은 다음과 같습니다.

 

1. 뽑은 과자의 총 개수가 두개일때 현재 가지고 있는 무게의 합을 리턴합니다.

2. 뽑은 과자의 개수가 두개가 안되는데 (최대 무게를 초과해 뽑지 못한상태) 모든 과자를 지나쳐왔다면 -1을 리턴합니다.

3. 과자를 뽑을 수 있는 상태일때 idx를 선택하는 경우와 아예 뽑지도 못하는 경우가 있습니다. idx번을 선택하는 경우에는 또 다시 idx번을 뽑는 경우와 idx번을 뽑지않는 경우가 있습니다. 이때 두 가지 분기점에서 최대값을 저장합니다.

4. 과자를 뽑을 수 있는 상태일때 idx를 무게가 초과하여 아예 뽑지 못하는 경우가 있습니다. 이 경우 idx+1 번 과자를 뽑으러 다음 단계로 들어갑니다.

 

Java 코드 - 재귀 함수 사용

package com.ssafy.off;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * 과자 두봉지 최대 무게 합
 * 1. 최대 M그램 이상
 * 2. 과자 한개당 두봉지 사야함.
 */
public class SWEA_9229_한빈이와SpotMart {
	static int answer;
	static int[] arr;
	static int MAX_WEIGHT;
	
	private static int solve(int idx, int cnt, int weight) {
		if(cnt < 2 && idx == arr.length) {
			return -1;
		}

		if(cnt == 2) {
			return weight;
		}
		
		//idx번 선택함
		if(weight+arr[idx] <= MAX_WEIGHT) {
			answer = Math.max(solve(idx+1, cnt, weight), solve(idx+1, cnt+1, weight+arr[idx]));
		}
		//idx번 선택못함
		else {
			answer = solve(idx+1, cnt, weight);	
		}
		
		return answer;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int TC = Integer.parseInt(br.readLine());
		for (int t = 1; t <= TC; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken()); // 과자봉지개수
			MAX_WEIGHT = Integer.parseInt(st.nextToken()); //무게 합 제한
			
			arr = new int[N]; // N개 과자 두봉지 무게 배열
			
			st = new StringTokenizer(br.readLine(), " ");
			
			for (int i = 0; i < N; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			answer = -1;
			int ans = solve(0,0,0);
			sb.append("#").append(t).append(" ").append(ans).append("\n");
			
		} // end of Test Case
		System.out.print(sb);
		
	}// end of main
}// end of class