[ boj : 1503 ] 세 수 고르기

www.acmicpc.net/problem/1503

1503번: 세 수 고르기

문제 : 집합 S에 속한 수들이 주어지고 N이 주어집니다. 이때, 집합 S에 속하지 않은 수들 중 x,y,z 를 선택하고 |N-xyz|의 값이 최소값을 구하시오

 

해설 : 문제 잘 읽고 오세요!!!

x,y,z는 중복이 가능한가 가능하지 않는가 문제에 나와있질 않지만 중복이 허용됩니다!!!!

n의 범위가 1000이니 가볍게 삼중포문을 통해 x,y,z를 확인하면서 경우의 수를 구하면 되겠죠.

그러나 주의할 점이 있습니다.

for문의 경계값을 전부 1000으로 설정하면 안된다는 것 입니다.

이유는 x,y,z가 될 수 있는 수의 범위는 1000을 넘어설 수 있기 때문이죠.

예를 들어 n이 1000이고 집합 S에 999와1000을 만들 수 있는 수들이 전부 존재할때 답은 |1000-1001| 이지만 for문의 경계값을 1000까지만 해놓으면 이상한 값을 도출하게 됩니다.

 

-------------------------------------------------------------------------------------------------

1000 25
2 5 10 25 50 125 250 500 625 100 1000 999 998 997 996 3 333 9 111 17 7 11 13 37 4

-------------------------------------------------------------------------------------------------

 

#include<bits/stdc++.h>

using namespace std;

int arr[1001];

int main()
{
	int n, m;
	int x;
	cin >> n >> m;
	for (int i = 0; i < m; i++)cin >> x, arr[x] = 1;

	int ans = (int)1e9;
	for (int i = 1; i <= 1000; i++) {
		if (arr[i] == 1)continue;
		for (int j = i; j <= 1000; j++) {
			if (arr[j] == 1)continue;
			for (int k = j; k <= 1001; k++) {
				if (arr[k] == 1)continue;
				ans = min(ans, abs(n - i * j * k));
			}
		}
	}
	cout << ans;
	return 0;
}