[SWEA 9229] 한빈이와 Spot Mart

문제

• SWEA 9229번
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

과자의 개수만큼 배열을 만들어 입력받은 각 과자를 저장한 후, 하나씩 인덱스를 돌면서 바로 다음 인덱스와 더한 값이 가장 최대값이면서 M을 넘지 않도록 한다. for문으로 돌려줄때 처음 for문은 i=0부터 N-1까지 과자를 하나 뽑아준다. 그리고 나서 아직 뽑지 않은 과자인 그 다음 인덱스부터 N-1까지 합을 구해주면 된다.
예를 들어 0번째 과자인 snacks[0]을 골랐다면 다음 과자인 snacks[1]부터 snacks[N-1]를 각각 snacks[0]과 더해보면서 현재 최대값인 maxWeight보다 크다면 maxWeight에 저장해준다. 이때 무게가 최대 M이어야 한다는 것을 명심하자. 만약 for문으로 모든 인덱스들을 한번 이상 선택했더라도 조건을 만족하는 최대값을 만족할 수 없는 경우에는 maxWeight의 초기값인 -1을 출력한다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Swea_9229 {

	static int T;
	static int N; // 개수
	static int M; // 무게
	static int[] snacks; // 과자 리스트
	static StringTokenizer st;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		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());

			snacks = new int[N];

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) 
				snacks[i] = Integer.parseInt(st.nextToken());
			
			int maxWeight = -1; // 고른 무게
			for(int i=0; i<N; i++) {
				for(int j=i+1; j<N; j++) {
					int tmp = snacks[i] + snacks[j];
					if((tmp > maxWeight) && (tmp <= M)) {
						maxWeight = tmp;
					}
				}
			}
			System.out.println("#"+tc+" "+maxWeight);
		}
	}
}