[Silver III] 세 수 고르기 - 1503 (브루트포스)

[Silver III] 세 수 고르기 - 1503

문제 링크

성능 요약

메모리: 114488 KB, 시간: 128 ms

분류

브루트포스 알고리즘(bruteforcing)

문제 설명

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

 

3시간만에 문제를 해결했다.. 해당 문제를 가장 최적화 시키기 위해 범위를 최대한 줄여보았다.

알고리즘은 30분 정도 걸려서 구현했는데, 생각지도 못한 부분이 많았다. 세세하게 설명이 필요한 문제다.

1. N(1<=N<=1000),M(0<=집합의 크기<=50)을 입력 받는다. - 범위 중요

2. 최솟값을 구해야하기 때문에 answer를 최대로 잡아준다. 132651인 이유는 집합의 크기를 50까지 받을 수 있기 때문에 가장 작은 자연수 1부터 50까지 사용하지 못하게 된다면, 51*51*51(132651)이 최소 값이 될 수 있기 때문이다. 

3.M이 0인 경우 모든 자연수를 사용할 수 있기 때문에 |N-1*1*N|을 해준다면 무조건 0이 나오기 때문에 0을 출력해주면 된다.

4.start에 넣은 값은 1~1000자연수 중에 사용할 수 있는 가장 최소 값을 가져온다. 그 이유는 최솟값을 뽑으려면 사용할 수 있는 가장 최소 값부터 시작해야 가능하기 때문이다.

5.집합 s에 들어있는 수는 해당 인덱스arr[i]에 False값을 줘서 브루트포싱을 할 때 continue로 넘겨버려 계산을 안하게 한다.

6.사용할 수 있는 가장 최소 값(start)이 10이상이면, xyz를 곱했을 때 최솟값이 1000이 되기 때문에 N의 최대 범위 이상인 수가 되므로 |N-start**3|이 최솟값이 된다.

7.사용할 수 있는 가장 최소 값(start)이 10미만이라면, start부터 세제곱해도 1000을 넘지 않는 9까지만 x값을 넣어주면  되고,  y는 제곱해도 1000을 넘지 않는 31까지만 넣어주면 되고, z는 start부터 1001까지 넣어주면 된다. 

7번에서 가장 많은 시간을 소요했는데, 그것은 바로 z 범위 때문이다. 보통 z를 start~1000까지 범위라고 생각할텐데 문제를 아주 아주 자세하게 보니 x,y,z 각각의 자연수 범위는 아예 주어지지 않았다. 그러므로 1000을 초과해서 최솟값을 구해도 되는 것이었다. 그럴 경우의 예시로 s에 999, 1000이 있을 경우 |1000-1*1*1001|로 최솟값이 1로 나올 수 있게 할 수 있다.

그러므로 s가 997,998,999,1000이런식으로 더 늘어나더라도 z가 1002보다 1001인 경우가 가장 최소이기 때문에 z의 범위를 더 늘이지 않고 1001까지만 잡아주면 해결이 가능했다.