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

문제

백준 18114번 - 블랙 프라이데이

해결 과정

• 하나씩 찾는게 아니라 이진탐색으로 찾아야 함
• 고른 물건이 1개, 2개, 3개일 때를 나누어서 생각하기
• 고른 물건이 1개일 때
  • weight에서 처음부터 끝까지 이진탐색으로 c값이 있는지 찾는다.
  • binarySearch(0, n - 1, c, weight)
• 고른 물건이 2개일 때
  • 2개 물건 더한 값인 sumW가 c와 같다면 바로 1을 리턴
  • c와 같지 않다면 3개일 때를 고려한다.
• 고른 물건이 3개일 때
  • 2개 물건 더한 값인 sumW이 c보다 크다면 j -= 1
  • 2개 물건 더한 값인 sumW이 c보다 작다면
    • diff = c - sumW
    • diff가 weight에 있는지 이진탐색으로 찾는다.

시행착오

• 시간 초과 !!!!!! why!!!!!!!!!!

import sys
from itertools import combinations
n, c = map(int,sys.stdin.readline().split())
weight = list(map(int,sys.stdin.readline().split()))

answer = 0
for i in range(1,4):
  for j in combinations(weight,i):
    if sum(j) == c:
      answer = 1
      break

print(answer)

• 함수로 구현해서 조건에 맞으면 바로 return하도록 했는데(함수 종료) but 또 시간 초과
• sum이 문제일까 ?? combinations이 문제인가?

import sys
from itertools import combinations
n, c = map(int,sys.stdin.readline().split())
weight = list(map(int,sys.stdin.readline().split()))

def solve(answer):
  for i in range(1,4):
    for j in combinations(weight,i):
      if sum(j) == c:
        answer = 1
        return answer
  return answer

print(solve(0))

• sum이랑 combination을 사용하지 않고 이중포문으로 무게 c - weight[i] + weight[j] 해당 값이 weight에 있으면 함수를 멈추고 리턴

import sys

n, c = map(int,sys.stdin.readline().split())
weight = list(map(int,sys.stdin.readline().split()))

def solve():
  if c in weight:
    return 1
  for i in range(n):
    for j in range(i+1,n):
      diff = c - weight[i] + weight[j]
      if c == weight[i] + weight[j]:
        return 1
      if diff in weight:
        if weight.index(diff) != i and weight.index(diff) != j:
          return 1
  return 0
        
print(solve())

풀이

import sys

def binarySearch(start,end,c,weight):
  while start <= end:
      mid = (start + end) // 2
      if weight[mid] == c:
          return mid
      if weight[mid] < c:
          start = mid + 1
      else:
          end = mid - 1
  return -1
  
def solve():
  # 고른 물건 1개
  if binarySearch(0, n - 1, c, weight) >= 0:
    return 1
  i = 0
  j = n - 1
  while i < j:
    sumW = weight[i] + weight[j]
    # 고른 물건이 2개일 때
    if sumW == c:
      return 1
    elif sumW > c:
      j -= 1
    else:
      diff = c - sumW
      # 고른 물건이 3개일 때
      if diff != weight[i] and diff != weight[j] and binarySearch(0, n - 1, diff, weight) >= 0:
        return 1
      i += 1
  return 0
  
n, c = map(int,sys.stdin.readline().split())
weight = list(map(int,sys.stdin.readline().split()))
weight.sort()      
print(solve())

https://velog.io/@ktaewon98/BaekjoonPython-18114%EB%B2%88-%EB%B8%94%EB%9E%99%ED%94%84%EB%9D%BC%EC%9D%B4%EB%8D%B0%EC%9D%B4