(Python/🥈2)백준 알고리즘 1503번: 세 수 고르기

 

문제 바로가기 

 

문제:

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

 

풀이:

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N, S = map(int,input().split())
lst = set([i for i in range(1, 1002)]) -set(list(map(int,input().split())))
ans = 1e9

for a in lst:
    for b in lst:
        for c in lst:
            ans = min(abs(N-a*b*c), ans)
            if N+1 < a*b*c:
                break
            print(a,b,c)
print(ans)

 

 

 

lst 에는 집합 S에 들어가는 값을 빼고 저장한다.

문제에서 2,4 가 S에 들어있으니 lst 에 2,4 제외하고 1~1001 까지 넣었다.

 

왜 문제에서 1000보다 같은 자연수인데 1001 은 넣었냐 ? 라는 의문이 있을 수 있다.

집합 S 에 들어있는 값이 1000보다 작은 수 이고, 우리가 고를 수 있는 수는 S 에 있는 자연수 제외 무한대 수이다.

따라서 1001 은 우리가 무조건 고를 수 있는 수이다. 그 중 가장 작은 수 이다. 

1000은 집합 S에 들어 있을 수도 있기 때문에 "무조건" 은 성립하지 않는다.

 

그리고 3중포문 진행

N+1 < a*b*c : 으로 쓸데없이 커지는 숫자는 브레이크로 넘긴다.