[BOJ] 1503 세 수 고르기 Python

import math
N,M = map(int,input().split())
A = list(map(int,input().split()))
num = []
for i in range (1,1050):
    if i not in A:
        num.append(i)
m = len(num)
val = 1e9
for i in range (0,m):
    if num[i] ** 3 > N + val:
        break
    for j in range (i,m):
        for k in range (j,m):
            val = min(val, int(math.fabs(N - num[i] * num[j] * num[k])))
print(val)

 

브루트포스로 계산하지만, 시간을 어떻게 더 단축할 수 있을지가 관건이었던 문제

 

 

추가 기재)

 

import math
N,M = map(int,input().split())
A = list(map(int,input().split()))
num = []
for i in range (1,1050):
    if i not in A:
        num.append(i)
m = len(num)
val = 1e9
for i in range (0,m):
    if num[i] ** 3 > N + val:
        break
    for j in range (i,m):
        if num[i] * num[j] * num[j] > N + val:
            break
        for k in range (j,m):
            val = min(val, int(math.fabs(N - num[i] * num[j] * num[k])))
print(val)

 

for j 에 있어서도 같이 제한 조건을 넣어줌으로서 훨씬 연산이 빨라진 것을 확인할 수 있었다 !