[Python/파이썬] 백준 18114번 블랙 프라이데이

18114번: 블랙 프라이데이

 

문제

서강 백화점이 블랙 프라이데이를 맞아서 특별 이벤트를 진행한다. 백화점에서 제시하는 양의 정수의 무게 C에 딱 맞게 물건들을 가져오면 전부 만 원에 판매하는 이벤트이다.

선택할 수 있는 물건은 최대 3개까지이고, 같은 물건을 중복 선택하는 것은 불가능하다. 그리고 백화점에서 판매하는 물건들의 무게는 모두 다르다.

예를 들어, 백화점에서 판매하고 있는 물건 5개의 무게가 각각 1, 2, 3, 4, 5일 때, C가 5라면 {2, 3} 또는 {5}에 해당하는 물건의 조합을 만 원에 구매할 수 있다.

판매하는 물건 N개의 양의 정수의 무게가 각각 주어질 때, 만 원에 구매할 수 있는 조합이 있는지 출력하라.

 

입력

첫 번째 줄에 물건의 개수 N과 제시하는 무게 C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ C ≤ 108, N과 C는 양의 정수)

다음 줄에는 N개의 물건 각각의 무게 w가 공백으로 구분되어 주어진다. (1 ≤ w ≤ 108, w는 양의 정수)

출력

문제의 조건을 만족하는 조합이 있으면 1, 그렇지 않으면 0을 출력한다.

코드

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
weight = sorted(list(map(int, input().split())))

def binary_search(start, end, target):
    while start <= end:
        mid = (start+end) // 2
        if weight[mid] == target:
            return True
        elif weight[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return False
    
# 1개
if binary_search(0, n-1, c):
    print(1)
    exit()

# 2개, 3개
left, right = 0, n-1
while left < right:
    two_sum = weight[left] + weight[right]
    if two_sum == c:   # 2개로 c 만들기
        print(1)
        exit()
    elif two_sum > c: 
        right -= 1
    else: 
        if binary_search(left+1, right-1, c - two_sum):   # 3개로 c 만들기
            print(1)
            exit()
        left += 1
print(0)

 

binary_search 함수는 시작인덱스, 끝인덱스, 찾으려는 값을 파라미터로 넘겨주면 그 값이 weight 배열에 존재하는지 찾아주는 함수이다. 파이썬에서는 bisect 라이브러리를 사용하면 위 코드처럼 함수를 구현하지 않아도 이분탐색 함수를 사용할 수 있다.

물건은 최대 3개까지만 선택할 수 있기 때문에 1, 2, 3개일 때를 각각 나누어 구했다.

• 이분탐색은 정렬된 배열에 대해 수행할 수 있으므로 weight 배열을 입력받을 때 정렬해야 한다.
• 1개일 때는 이분탐색을 통해 weight 배열에 c와 같은 무게를 갖는 물건이 있는지 확인한다. 
• 2, 3개일 때는 left와 right의 초기값을 각각 0, n-1로 설정하고 2개의 무게 합(two_sum)이 c와 같은 경우가 있는지 확인한다. 이때 two_sum 값이 c보다 크다면 무게를 줄여야 하므로 right 값을 감소시킨다. two_sum이 c보다 작다면 3개를 더해서 c와 같은 값이 되는 경우가 있는지 확인하기 위해 binary_search(left+1, right-1, c - two_sum)를 수행한다. 만약 c와 같은 값을 만들 수 없다면 left를 증가시켜준다.

 

처음에 생각했던 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

n, c = map(int, input().split())
weight = list(map(int, input().split()))

def dfs(idx, cnt, total):
    if total == c:
        print(1)
        exit()
    if idx >= n or cnt >= 3 or total >= c:
        return
    # idx번째 물건 포함 O
    dfs(idx+1, cnt+1, total+weight[idx])
    # idx번째 물건 포함 X
    dfs(idx+1, cnt, total)

dfs(0, 0, 0)
print(0)

처음에는 i번째 물건을 담기/담지 않기 2가지 경우로 하여 dfs를 이용하여 풀이하려고 했는데 시간 초과로 통과하지 못했다. 그래서 어차피 물건은 3개까지만 담을 수 있기 때문에 정답으로 제출한 위 코드와 같이 3가지 경우로 나누어 이분탐색을 이용하여 풀이하였다.