[코드트리/NOVICE MID] 특정 수와 근접한 합 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
 
        int[] arr = new int[N];
        int total = 0;    // 배열 값들의 총합
 
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            total += arr[i];
        }
 
        int diff = Integer.MAX_VALUE; // 최소 차이
        for(int i = 0 ; i < N ; i++) {
            for(int j = i + 1 ; j < N ; j++) {  // 제외시킬 번호1
                for(int k = j + 1 ; k < N ; k++) {  // 제외시킬 번호2
                    if(Math.abs(S - (total - arr[j] - arr[k])) < diff) {
                        diff = Math.abs(S - (total - arr[j] - arr[k]));
                    }
                }
            }
        }
 
        System.out.println(diff);
    }
}

 

 

🧩  해결 아이디어

• 완전탐색

- 제외할 원소의 두 위치를 일일이 잡는다.

- '배열 총합 - 해당 두 위치에서의 원소값' 한 차이값이 현재 최소 차이값 diff 보다 작다면, 이를 갱신한다.

 

 

 

---

💬 느낀 점

빠르게~~

 

1회독	2회독	3회독	4회독	5회독
V