(Python)백준 코딩테스트 연습 - 세 수 고르기(1503)

1. 문제

https://www.acmicpc.net/problem/1503

1503번: 세 수 고르기

2. 풀이

import sys
input = sys.stdin.readline

# n : target 자연수
# m : 집합의 크기
n, m = map(int, input().split())

# s : 자연수 집합
s = list(map(int, input().split()))
# sList : 집합에 자연수가 포함되어 있는지 확인하는 bool 리스트
sList = [False for i in range(0, 1002)]
for i in s:
    sList[i] = True

# minMultiNum : target 자연수와의 차이 중 최솟값
minMultiNum = 2147483647

for i in range(1, 1002):
    if sList[i]: continue
    for j in range(i, 1002):
        if sList[j]: continue
        multiNum = i * j
        for v in range(j, 1002):
            if sList[v]: continue
            absMultiNum = abs(n - multiNum * v)
            minMultiNum = min(minMultiNum, absMultiNum)
            if(n+1 < multiNum * v): break
        if minMultiNum == 0:
            break
    if minMultiNum == 0:
        break
        
print(minMultiNum)

3. FeedBack

 - 오래걸린 문제이다.

 브루트포스 알고리즘으로 3중 반복문을 사용하다 보니, 중간중간 continue나 break 조건을 확실히하여 시간초과를 잡는게 중요 포인트였다.