4/8 Coding Test

✅ 문제 풀이 - BOJ (이분 탐색)

🎈 2776 암기왕

기억력 테스트를 하고자 m개의 질문을 던진다고 한다. 이때 질문의 내용은 x라는 정수를 본 적이 있는가? 를 뜻하고 각 수에 대해 수첩1에 정수 x가 존재하면 1을, 없으면 0을 출력하는 문제
입출력은 다음과 같다.

• 입력: 첫 줄에 테케 수 t, 둘째 줄에는 수첩 1에 적힌 정수 개수 n, 셋째 줄에는 수첩 1에 적힌 정수들이 들어오고, 넷째 줄에는 수첩 2에 적힌 정수 개수 m, 마지막 줄에는 수첩 2에 적힌 m개의 정수들이 입력된다.
• 출력: 수첩2에 적힌 m개의 숫자 순서대로 숫자 1에 있으면 1, 없으면 0을 출력

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n = int(input())
    note1 = set(map(int, input().split()))
    m = int(input())
    note2 = list(map(int, input().split()))
    for i in note2:
        if i in note1:
            print(1)
        else:
            print(0)

< 풀이 과정 >
주어진 문제 그대로 구현하면 해결되는 문제.
note2를 for문을 돌려 앞에서붜 각 원소 별 note1에 존재하면 1을, 아니면 0을 출력하는 문제

🎈 2792 보석상자

각 보석은 m가지 서로 다른 색상 중 한 색상이고, 모든 보석을 n명에게 나눠 주려 한다.
이때 보석을 못받은 학생도 존재하고, 학생은 학상 같은 색상의 보석만 가져간다.
한 아이가 너무 많은 보석을 가져가면 타 학생이 질투를 하는데, 이때 질투심은 가장 많은 보석을 챙긴 학생이 가진 보석 수를 의미한다.
결론적으로, 보석 수를 최소화하면서 모든 학생에게 보석을 나누어 주는 방식을 프로그램으로 작성하는 문제
입출력은 다음과 같다.

• 입력: 첫 줄에 학생 수 n, 보석 색상 수 m이 주어지고 다음 m줄에는 양의 정수가 주어지며 k번째 줄에 있는 숫자는 k번 색상 보석 개수를 의미한다.
• 출력: 질투심의 최솟값

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
jewel = []
for _ in range(m):
    jewel.append(int(input()))
left = 1
right = max(jewel)
while left <= right:
    mid = (left + right) // 2
    person = 0
    for i in jewel:
        if i % mid == 0:
            person += i // mid
        else:
            person += (i//mid) + 1
    if person > n:
        left = mid + 1
    else:
        right = mid - 1
print(left)

< 풀이 과정 >
n, m, m줄만큼의 jewel을 입력받은 후 left를 질투심 최솟값으로 보고, right를 주어진 jewel의 max값으로 저장하여 while 루프를 돈다.

• mid 값으로 중앙값을 선정한 후 나눠받은 학생 수를 person으로 저장한다.
• 각 jewel마다 색상이 동일하게 나눠야 하는 것은 즉 1개만 있으면 한사람만 가질 수 있음을 의미하기에 각 보석마다 for문을 사용해준다.
• 각 색상이 다른 보석 별로 mid를 나누어 몫을 person 수로 계산하고 나누어 떨어지지 않으면 어쨌든 모든 보석을 나눠줘야 하기에 person 수에 + 1을 진행한다.
• 더해준 person 사람 수가 주어진 n보다 크면 질투심을 1씩 늘려주고, 반대의 경우 max값을 낮춰가며 보석을 최대한 동일한 개수로 나눠주도록 한다.