10815: 숫자 카드

set 이용

# 숫자 카드
# set 이용 - 648

import sys

sys.stdin = open("input.txt","r")

input = sys.stdin.readline

N = int(input())
a = set(map(int, input().split()))
M = int(input())
b = list(map(int, input().split()))

for x in b:  # M개의 숫자카드에 대해서
  if a & set([x]):
    print("1", end=' ')
  else:
    print("0", end=' ')
print()

이진탐색 ver → 시간초과… → if x == a[mid]: 여기서 break 추가해주니까 안난다.. start end가 바뀌지 않으니까 빠져나가야한다!

# 숫자 카드
# binary search (=이분탐색=이진탐색)
# 시간 초과.....

import sys

sys.stdin = open("input.txt","r")

input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))

M = int(input())
b = list(map(int, input().split()))

a.sort()  # 이진탐색을 위해 a의 데이터 정렬
for x in b:  # M개의 숫자카드에 대해서
  start, end = 0, N-1
  result = 0
  while start <= end:
    mid = (start + end) // 2
    if x == a[mid]:
      result = 1
			break # 이거 안넣어줘서 시간초과났다~!~!!~~!
    elif x < a[mid]:  # target이 중간점보다 왼쪽에 있다면
      end = mid - 1
    else:  # target이 중간점보다 오른쪽에 있다면
      start = mid + 1
  print(result, end = ' ')

2512: 예산

import sys

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
arr.sort()
M = int(input())

maxBudget = -1

if sum(arr) <= M:  # 모든 요청이 배정될 수 있는 경우 -> 요청한 금액 그대로 배정
  maxBudget = max(arr)

else:  # 모든 요청이 배정될 수 없는 경우 -> 상한액 정하기
  low, high = 0, max(arr)
  while low <= high:
    mid = (low + high) // 2
    # mid를 상한액으로 해서 예산을 배정하고,
    # 총 예산이 M 이상이면 -> high를 바꿔
    # M보다 작으면 -> low를 바꿔
    sum = 0
    for i in range(N):
      if arr[i] > mid:
        sum += mid
      else:
        sum += arr[i]
    if sum <= M:
      low = mid + 1
    else:
      high = mid - 1
  maxBudget = high

print(maxBudget)

3079: 입국심사

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
time = [int(input()) for _ in range(N)]

left, right = 1, M*(min(time))
result = 0
while left <= right:
  mid = (left + right)//2
  sum = 0
  for t in time:
    sum += (mid // t)
  if sum < M:
    left = mid + 1
  else:
    right = mid - 1
    result = mid
print(result)

사람 수에 맞는 입국 심사 시간의 최솟값을 바로 구하기 어려우므로, 역으로 특정 시간이라고 가정을 먼저 하고 가능한 사람 수가 맞는지 확인한다 (?)

1. 입국심사시간의 최솟값을 mid라 가정한다.
2. 그 mid값을 각 입국심사대의 소요시간으로 나누고, 그 값들을 모두 합하면 가능한 사람 수가 나온다.
3. 가능한 사람 수가 M명보다 많으면 그 시간이 가능한것이고, M명보다 적으면 불가능한 것이다.

ㅜㅜ 설명을 어떻게 해야할지 모르겠다..

도움이 된 블로그의 설명:

입국 심사 시간을 인자로 받아 몇 명을 심사할 수 있는지를 체크하는 함수를 작성