[백준] 블랙 프라이데이(18114) - python

문제

서강 백화점이 블랙 프라이데이를 맞아서 특별 이벤트를 진행한다. 백화점에서 제시하는 양의 정수의 무게 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을 출력한다.

예제 입력 1 

5 5
1 2 3 4 5

예제 출력 1 

1

예제 입력 2 

3 13
3 7 8

예제 출력 2 

0

---

<코드 제출 1> 

import sys
from itertools import combinations, chain
input = sys.stdin.readline

N, C = map(int, input().split())
weights = list(map(int, input().split()))
coms, sums = [], []

for i in range(1, 4):
    coms.append(list(combinations(weights, i)))
    
coms = list(chain.from_iterable(coms))

for i in coms:
    sums.append(sum(i))

if C in sums:
    print(1)
else:
    print(0)

시간 초과

1. coms.append(list(combinations(weights, i))) -> coms에 list를 append하면 coms는

[[(1,), (2,), (3,), (4,), (5,)], [(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)], [(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)]]

이런식으로 리스트 자체가 들어간다. (리스트 안에 리스트)

이걸 하나의 리스트로 만들려고 chain을 사용했는데 이렇게 할 필요 없이 extend로 한번에 처리 가능

=> coms.extend(combinations(weights, i))

 

<코드 제출 2>

import sys
from itertools import combinations
input = sys.stdin.readline

N, C = map(int, input().split())
weights = list(map(int, input().split()))
coms, sums = [], []

for i in range(1, 4):
    coms.extend(combinations(weights, i))

for i in coms:
    sums.append(sum(i))

if C in sums:
    print(1)
else:
    print(0)

여전히 시간초과

1. sums라는 리스트를 만든 후 C 가 그 안에 있는지 비교하지 말고 coms의 원소 중 C인게 있으면 바로 1 출력하고 반복문 멈추기

 

<코드 제출 3> 

import sys
from itertools import combinations
input = sys.stdin.readline

N, C = map(int, input().split())
weights = list(map(int, input().split()))
coms = []
answer = 0

for i in range(1, 4):
    coms.extend(combinations(weights, i))

for i in coms:
    if sum(i) == C:
        answer = 1
        break
print(answer)

시간 초과...

1. coms라는 리스트도 만들지 말고 첫번째 for문에서 sum까지 다 해보자

 

<코드 제출 4> 

import sys
from itertools import combinations
input = sys.stdin.readline

N, C = map(int, input().split())
weights = list(map(int, input().split()))
coms = []
answer = 0

for i in range(1, 4):
    for comb in combinations(weights, i):
        if C == sum(comb):
            answer = 1
            break
print(answer)

또 또 시간초과

1. combinations를 쓴게 잘못인 것 같다. 가능한 모든 조합을 생성하기 때문에 시간 복잡도가 O(2^N)에 가까움->  입력이 커지면 비효율적일 것.

=> 다른 코드 참고 하겠음

---

 

이진 탐색 binary search

알고리즘 수업시간에 배운건데 문제 풀 때 적용을 하나도 못했다.

2025.01.09 - [알고리즘] - 이진 탐색(Binary Search)

 

<코드 제출 5>

import sys
input = sys.stdin.readline
N, C = map(int,input().split())
weights = list(map(int,input().split()))
weights.sort()

def binary_search(left,right,diff):
    while left <= right:
        mid = (left + right) // 2
        if weights[mid] == diff:
            return 1
        elif weights[mid] > diff:
            right = mid - 1
        else:
            left = mid + 1
    return 0

def check(N, C):
    if C in weights:
        return 1
    i, j = 0, N-1
    while i < j:
        total = weights[i] + weights[j]
        if total > C:
            j -= 1
        elif total == C:
            return True
        else:
            diff = C - total
            if weights[i] != diff and weights[j] != diff and binary_search(i,j,diff):
                return True
            i += 1
          
if check(N, C):
    print(1)
else:
    print(0)

결과

binary search 구현 코드는 외워두기!