[백준] 1503번 : 세 수 고르기 (C++)

1503번 : 세 수 고르기

---

 

문제)

M개의 자연수로 이루어진 집합 S와 자연수 N이 주어진다.

S에 속하지 않는 자연수 x, y, z를 골라서, |N - xyz|의 최솟값을 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 N(1 ≤ N ≤ 1,000)과 집합 S의 크기 M(0 ≤ M ≤ 50)이 주어진다. 둘째 줄에는 집합 S에 들어있는 수가 주어진다. 집합에 들어있는 수는 1,000보다 작거나 같은 자연수이고, 공백으로 구분되어져 있다. 또, 중복되는 수는 없다.

집합의 크기가 0인 경우에는 둘째 줄은 빈 줄이다.

 

 

 

출력 :

첫째 줄에 |N - xyz|의 최솟값을 출력한다.

 

 

 

 

 

풀이)

 

// 1503. 세 수 고르기
#include <iostream>
#include <climits>
#include <algorithm>
 
using namespace std;
 
int n, m;
bool arr[1001];
int temp[3];
int ans = INT_MAX;
 
void recur(int cur, int idx)
{
    if (cur == 3)
    {
        int xyz = temp[0] * temp[1] * temp[2];
        
        ans = min(ans, abs(n - xyz));
        return;
    }
 
    for (int i = idx; i < 1003; i++)
    {
        if (i < 1001 && arr[i]) continue;
        temp[cur] = i;
        recur(cur + 1, i);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    int a;
    for (int i = 0; i < m; i++)
    {
        cin >> a;
        arr[a] = 1;
    }
 
    recur(0, 1);
 
    cout << ans;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/1503 

1503번: 세 수 고르기