BOJ 1503 - 세 수 고르기

문제

집합 S에 포함되지 않는 세 자연수를 골라, 그 곱과 N의 차이의 절댓값을 최소화하라.

입력

첫째 줄에 N과 집합의 크기 M, 둘째 줄에 집합 S의 원소가 주어진다 (M이 0이면 둘째 줄 없음).

출력

|N - i*j*k|의 최솟값을 출력한다.

예제

입력	출력
`10 2` `2 3`	`0`

풀이

1부터 1001까지의 수 중 S에 없는 수 세 개의 곱으로 N에 가장 가까운 값을 찾는 브루트포스이다.

3중 반복문으로 S에 포함되지 않는 세 수 i, j, k를 선택한다
|N - i*j*k|를 계산하여 최솟값을 갱신한다
ijk가 N+1을 초과하면 k 루프를 중단하는 가지치기를 적용한다

핵심 아이디어: 곱이 N을 초과하면 k가 커질수록 차이도 커지므로 break로 가지치기하면 실제 탐색량이 크게 줄어든다.

코드

import sys
 
input = sys.stdin.readline
INF = sys.maxsize
 
n, m = list(map(int, input().rstrip().split()))
s = list(map(int, input().rstrip().split()))
res = INF
 
for i in range(1, 1002):
    if i in s:
        continue
    for j in range(1, 1002):
        if j in s:
            continue
        for k in range(1, 1002):
            if k in s:
                continue
            q = i * j * k
            if abs(n - q) < res:
                res = abs(n - q)
            if n + 1 < q:
                break
 
print(res)

복잡도

시간: O(1001^3) (가지치기로 실제 수행 시간은 크게 감소)
공간: O(M) (M은 집합 S의 크기)

문제