문제
서강 백화점이 블랙 프라이데이를 맞아서 특별 이벤트를 진행한다. 백화점에서 제시하는 양의 정수의 무게 C에 딱 맞게 물건들을 가져오면 전부 만 원에 판매하는 이벤트이다.
선택할 수 있는 물건은 최대 3개까지이고, 같은 물건을 중복 선택하는 것은 불가능하다. 그리고 백화점에서 판매하는 물건들의 무게는 모두 다르다.
예를 들어, 백화점에서 판매하고 있는 물건 5개의 무게가 각각 1, 2, 3, 4, 5일 때, C가 5라면 {2, 3} 또는 {5}에 해당하는 물건의 조합을 만 원에 구매할 수 있다.
판매하는 물건 N개의 양의 정수의 무게가 각각 주어질 때, 만 원에 구매할 수 있는 조합이 있는지 출력하라.
import sys
input = lambda: sys.stdin.readline().strip()
n, c = map(int, input().split())
check = 0
arr = list(map(int, input().split()))
arr.sort()
item1, item2, item3 = 0, 0, 0
for i in range(n):
item1 = arr[i]
if item1 == c:
check = 1
break
start, end = i + 1, n - 1
mid_index = 0
while start <= end:
mid = (start + end) // 2
item2 = arr[mid]
num = item1 + item2
if num == c:
check = 1
break
elif num > c:
end = mid - 1
else:
start2, end2 = i + 1, mid - 1
while start2 <= end2:
mid2 = (start2 + end2) // 2
item3 = arr[mid2]
num = item1 + item2 + item3
if num == c:
check = 1
break
elif num < c:
start2 = mid2 + 1
else:
end2 = mid2 - 1
if num == c:
break
start = mid + 1
if check == 1:
break
print(check)풀이
- 첫번째 물건 : 반복문을 통한 설정
- 두번째 물건 : 이진 탐색을 통한 설정
- 세번째 물건 : 두번째 물건을 찾는 과정에서 무게가 부족하다면 첫번째 물건과 두번째 물건사이에서 이진 탐색을 통해 설정
