[Java] SWEA9229_한빈이와 Spot Mart

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW8Wj7cqbY0DFAXN 

SW Expert Academy

[문제]

한빈이는 퇴근길에 스팟마트에 들러 과자 두 봉지를 사서 양 손에 하나씩 들고 가려고 한다.

 

스팟마트에는 N개의 과자 봉지가 있으며, 각 과자 봉지는 ai그램의 무게를 가진다.

 

배가 많이 고픈 한빈이는 최대한 양이 많은 (무게가 많이 나가는) 과자 봉지를 고르고 싶으나,

과자 두 봉지의 무게가 M 그램을 초과하면 무거워서 과자를 들고 다닐 수 없다.

 

한빈이가 들고 다닐수 있는 과자들의 최대 무게 합을 출력하라. 한빈이는 과자를 “정확히” 두 봉지 사야 함에 유의하라.

 

[입력]

4                   //테스트케이스
3 45               //과자 개수, 무게제한
20 20 20         // 과자무게 
6 10
1 2 5 8 9 11
4 100
80 80 60 60
4 20
10 5 10 16

 

[출력]

#1 40
#2 10
#3 -1
#4 20

 

[풀이]

과자 N개중에서 2개를 뽑는 조합문제이다.

(과자를 선택하는데에 있어 순서는 중요하지 않으므로 순열은 x)

재귀함수를 돌려 조합을 구할까 하다가 2개만 뽑는거라 for문을 돌리는게 더 간단한 코드가 될 것 같아 이중for문을 이용하여 최대 무게가 되는 과자의 조합을 구해주었다. 

(조합의 정의와 재귀함수를 이용하여 조합을 구하는 코드는 아래 링크 클릭!)

https://java-is-happy-things.tistory.com/7?category=1266501 

[Java] 조합

 

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

//swea9229

public class SWEA9229 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		System.setIn(new FileInputStream("src//day04//hw//9229.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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());	//과자갯수
			int M = Integer.parseInt(st.nextToken());	//제한무게
			
			//과자배열 생성
			int[] arr = new int[N];
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<N; i++) {					
				arr[i]=Integer.parseInt(st.nextToken());
			}
			int max=0;
			int num=0;
			for(int i=0; i<N-1; i++) {
				for(int j=i+1; j<N; j++) {
					num  = arr[i]+arr[j];
					if(num>max && num<=M) max=num;		
					
				}
			}
			if(max==0) {
				System.out.printf("#%d %d\n",t,-1);
			}else {
				System.out.printf("#%d %d\n",t,max);
			}
			
			
		}
	}
	
}