🌈 9월 2주차 실력진단 결과

나는 일주일 전 487점이였는데 이번에 몇 점일까?!
점수 떨어짐...ㅋㅋㅋㅋㅋㅠㅠ
2차원 배열 문제가 나왔는데 시간 안에 못 풀었다..(그 문제 다시 풀고싶다..)
풀 수 있는 문제였더라도 내가 시간 안에 못 풀었으니 점수가 떨어질 수 밖에 없었을 듯..! 떨어지니까 맘 아프다... 더 열심히 해야지...!!! 😹

이번 주차는 완전 탐색 알고리즘을 공부하는 중이다!
완전 탐색은 가능한 모든 경우의 수를 탐색해서 정답을 찾는 방법이다.
Brute Force(브루트 포스)라고도 하는데 이는 무식하게 힘써서 한다는 뜻.. 모든 경우의 수를 탐색하기 때문에 정확도 100%의 암호 해독법으로 매우 강력한 방법이다!!

오늘은 그 중에서도 완전탐색 1에 있는 마지막 문제를 가져왔다!
완전 탐색 공부를 했다면 그리 어렵지 않을 문제인듯..!

☝️ 특정 수와 근접한 합 문제

코드 트리 문제 링크

문제

정수 S와 N개의 수가 주어지면, N개의 수들 중 정확히 2개를 제외하여 남은 N-2개의 숫자들의 합이 S와 최대한 가까워지도록 하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 N과 S가 공백을 사이에 두고 주어집니다.
두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

3 ≤ N ≤ 100
1 ≤ S ≤ 10,000
1 ≤ 주어지는 수 ≤ 100

출력 형식

2개를 제외하여 나올 수 있는 합 중 S와 가장 가까운 경우에 대해 두 값이 차이를 출력합니다.

✌️ 문제 생각해보기

크게 두 가지를 생각하면 되겠다!
1. 가능한 두 개의 원소를 빼고 모두 더하기
2. 1에서 더한 값과 S의 차이가 가장 작은 차이값 찾기

입력 예시가 5 7 9 1 13 8 일 때,
빼 낼 두 개의 원소를 쌍으로 표현하면
(5, 7), (5, 9), (5, 1), (5, 13), (5, 8)
(7, 9), (7, 1), (7, 13), (7, 8)
(9, 1), (9, 13), (9, 8)
(1, 13), (1, 8)
(13, 8) 이다.

이를 제외하고 모든 원소를 더했을 때 값을 sum에다 저장하고
이 sum 값과 S의 차이를 구한 뒤 이게 더 작을 때 min_val을 갱신한다.

🤟 코드 구현하기

#include <iostream>
#include <climits>
#include <algorithm>

using namespace std;

int main() {
    int n, s;
    cin >> n >> s;

    int arr[100];
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }

    int min_val = INT_MAX;
    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            int sum = 0;
            for(int k=0; k<n; k++){ //두 개 원소 빼고 모든 원소 더하기
                if(k == i || k == j){
                    continue;
                }
                sum += arr[k];
            }
            min_val = min(min_val, abs(sum-s)); //더한 값과 S의 차이를 구하고 더 작을 경우에 갱신한다.
        }
    }
    cout << min_val;

    return 0;
}