[SW] [D3] [DFS][조합] 9229. 한빈이와 Spot Mart

9229. 한빈이와 Spot Mart

SW Expert Academy

 

• 내 풀이 - java

package day7_bfs;

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

public class SW9229_ParkSomin {
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        int T=Integer.parseInt(st.nextToken());
        for (int test_case = 1; test_case <=T; test_case++) {
            st=new StringTokenizer(br.readLine());
            int n=Integer.parseInt(st.nextToken());
            int max=Integer.parseInt(st.nextToken()); //최대 무게

            int[] snack= new int[n];
            st=new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                snack[i]=Integer.parseInt(st.nextToken());
            }

            Arrays.sort(snack);

            int point=0;
            int sum=0;
            int idx=n-1;
            while (true){
                int last=snack[idx];
                int front=snack[point];
                if(idx<=point){
                    if(sum==0){
                        sum=-1;
                    }
                    break;
                }

                if (last+front>max){
                    idx--;
                    continue;
                }
                //넘지않은 경우
                sum=Math.max(sum, last+front);
                point++;
            }

            System.out.printf("#%d %d", test_case,sum);
            System.out.println();

        }
    }
}

 

• 다른 사람 풀이1
  • 수정할 필요없이 처음 생성 시 max=-1 해놓으면 됨
  • for문 2번 돌면서 전부 더해서 값 확인
    • 첫번째 for문 j : 0~N
    • 두번째 for문 k: j+1~ N 

package asd;
import java.util.Scanner;

public class SW9229_ChoiYongtae {

	public static void main(String[] args) {
		int T,N,M;
		int[] arr;
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for(int i=1;i<=T;i++) {
			N = sc.nextInt();
			M = sc.nextInt();
			arr = new int[N];
			for(int j=0;j<N;j++) {
				arr[j] = sc.nextInt();
			}
			int max = -1;
			for(int j=0;j<N;j++) {
				for(int k=j+1;k<N;k++) {
					if(arr[j]+arr[k]<=M) {
						max = Math.max(max, arr[j]+arr[k]);
					}
				}
			}
			System.out.println("#"+i+" "+max);
		}
	}

}

 

• 다른 사람 풀이 2 - 조합, dfs
  • 여러개 중 2봉지만 조합해서 sum 계산

package com.day7;

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

import java.util.*;

public class SW9229_Jisangil {
    static int max;
    static int n;
    static int m;
    static List<Integer> a;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());

        for (int i = 0; i < tc; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            max = -1;
            a = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                a.add(Integer.parseInt(st.nextToken()));
            }
            dfs(0, 0, 0);

            System.out.println("#" + (i + 1) + " " + max);

        }

    }

    private static void dfs(int depth, int sum, int start) {
        if (depth == 2) {
            if (sum > m) {
                return;
            }
            max = Math.max(max, sum);
            return;
        }
        for (int i = start; i < n; i++) {
            dfs(depth + 1, sum + a.get(i), i + 1);
        }
    }
}