[SWEA] 9229:한빈이와 Spot Mart (Java 자바)

풀이 및 소스코드

 

답이 완벽한 것 같은데 계속 틀렸다고 나와서 그만뒀다가 다시 푼 문제..

과자를 2개 밖에 들지못하는 한빈이가 이해가 되지 않아서 틀렸던 문제였다..

만약 과자를 두개 들었다면 종료하는 조건을 추가해주니 바로 성공했다 ㅋㅋㅋㅋ 아 어이없어 ..

파이썬에는 combination이나 permutation을 사용하여 내가 직접 구현하지 않아도 경우의 수를 전부 구할 수 있었으나,

자바에서는 재귀를 사용해야한다.

재귀를 사용하기 위해서 계속 쓰이는 n, m, 과자의 무게가 담기는 snack int 배열, 그리고 최대 무게를 출력할 max와 같은 변수들은 static 으로 메소드 위에 선언해준다.

현재 총 무게 0, cnt(한빈이가 들지 말지 고려할 과자의 snack 인덱스) = 0, 한빈이가 들기로 결정한 과자의 수 = 0 으로 recur 메소드를 실행시킨다.

recur 메소드를 통해 현재 cnt값을 인덱스로 보고, 들기로 결정한 것과 들지 않기로 결정한 이 두 가지 경우의 수로 recur가 계속 반복된다.

들기로 결정했다면 현재 총 무게에는 원래무게 + snack[cnt] 값이 들어가고, cnt +1, 한빈이가 들기로 결정한 과자의 수+1 이 되어 돌아가게 되고, 들지 않기로 결정했다면 현재 총 무게는 변하지 않은 원래무게, cnt+1(다음꺼도 고려해줘야하기 때문.), 한빈이가 들기로 결정한 과자의 수도 원래대로 들어가게 된다.

이렇게 돌다가, 한빈이가 들기로 한 과자의 무게가 한빈이의 한계 무게를 넘으면 그냥 종료.

한빈이가 2개를 이미 들었거나, cnt 가 arr 길이보다 커질 경우 현재 한빈이가 들고 있는 과자의 합과 max 값을 비교해 큰 값을 max에 넣어주고 재귀를 끝낸다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	static int n,m;
	static int[] snack;
	static int max;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int t = Integer.parseInt(br.readLine());
		for(int tc=1;tc<=t;tc++) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			max = -1;
			snack = new int[n];
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<n;i++) {
				snack[i]= Integer.parseInt(st.nextToken());
			}
			recur(0, 0, 0);
			sb.append("#").append(tc).append(" ").append(max).append("\n");
		}
		System.out.println(sb);

	}
	public static void recur(int total_w, int cnt, int select_cnt) {
		if(total_w>m) {
			return;
		}
		if(select_cnt==2||cnt == n) {
			if(m>=total_w && select_cnt>=2) {
				max = Math.max(max, total_w);
			}
			return;
		}
		recur(total_w+snack[cnt], cnt+1, select_cnt+1);
		recur(total_w, cnt+1, select_cnt);
	}

}