[백준 1503번] 세 수 고르기

[백준 1503번] 세 수 고르기

www.acmicpc.net/problem/1503

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|의 최솟값을 출력한다.

 

 

 풀이

#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, M;
	bool arr[1002] = {false,};
	vector<int> v;
	cin >> N >> M;
	
	for(int i=0;i<M;i++){
		int a;
		cin >> a;
		arr[a] = true;
	}
	
	for(int i=1;i<1002;i++){
		if(!arr[i]) v.push_back(i);
	}
	
	int result = 2147483647;
	int sz = v.size();
	for(int i=0;i<sz;i++){
		for(int j=0;j<sz;j++){
			for(int k=0;k<sz;k++){
				int q = v[i]*v[j]*v[k];
				if(abs(N-q) < result) result = abs(N-q);
				if(N+1 < q) break;
			}
		}
	}
	cout << result;
	return 0;
}

 완전 탐색 문제로 3중 반복문으로 풀긴했지만 만약 문제의 범위가 달랐더라면 어떻게 풀어야 할까 생각이 드는 문제였다. 문제 그대로 집합 M에 포함안되는 숫자들로 3중 for문을 돌려서 풀었다. 데이터가 부족했는지 1000*1000*1000에도 시간초과가 나지 않았다. break로 충분히 시간을 단축시킬 수 있었다. 문제를 풀면서 간과했던 부분이 M개의 원소들의 범위가 1000까지라 당연히 자연수의 범위도 1000인줄 알고풀었다가 한동안 헤매었다. N의 범위가 1000까지라 1001까지만 허용하면 쉽게 해결되었다.