해설

• 숫자 M 개만큼 주어지는데 이중에 3개를 골라 더하는데,
• <더한 숫자>가 <목표하는 수 N>에 가장 근접하는 경우를 찾는 문제
• N제한이 100으로 작아서 100^3 = 1000000 백만번인데, 이정도는 충분히 시간안에 도는 문제라 3중 포문으로 풀었다.
• 같이 공부하는 어거스트가 백트레킹 방식을 추천해줘서 백트래킹으로도 풀었다.
• 백트레킹도 딱히 성능상의 장점은 없었다.

첫번째 3중포문

import java.io.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int arr[] = new int[101];
        int numCard = sc.nextInt();
        int target = sc.nextInt();
        int diff = 300000;

        for(int i=0 ; i<numCard ; i++) {
            arr[i] = sc.nextInt();
        }

        int sum = 0;
        int curGap = 0;
        int answer =0;
        for(int i=0 ; i<numCard ; i++) {
            for(int j=i+1 ; j<numCard ; j++) {
                for(int k=j+1 ; k<numCard ; k++) {
                    sum = arr[i] + arr[j] + arr[k];
                    curGap = target - sum;
                    if(( curGap >= 0 ) && (curGap < diff)) {
                        diff = curGap;
                        answer = sum;
                        if(sum == target) {
                            System.out.println(answer);
                            return;
                        }
                    }
                }
            }
        }

        System.out.println(answer);
        return;


    }
}

두번째 백트레킹

• 백트레킹 방식 풀이

import java.io.IOException;
import java.util.Scanner;

public class Main {

    static int target = 0;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int numCard = sc.nextInt();
        target = sc.nextInt();
        int diff = 300000;
        int arr[] = new int[numCard];
        boolean used[] = new boolean[numCard];
        int[] temp = new int[3];
        int[] answer = new int[1];


        for (int i = 0; i < numCard; i++) {
            arr[i] = sc.nextInt();
        }

        permu(0,used,arr,temp,answer);

        System.out.println(answer[0]);
    }

    public static void permu(int dep,boolean[] used, int[] arr,int[] temp, int[] answer) {

        if(dep == 3) {
            int sum = temp[0] + temp[1] + temp[2];
            if(sum <= target) {
                answer[0] = Math.max(sum,answer[0]);
            }
        }
        else {
            for(int i=0 ; i<used.length ; i++) {
                if(used[i] == false) {
                    used[i] = true;
                    temp[dep] = arr[i];
                    permu(dep+1,used,arr,temp,answer);
                    used[i] = false;
                }
                else {
                    //continue;
                }
            }
        }
        return ;
    }


}