[Softeer] 21년 재직자 대회 본선 - 코딩 테스트 세트 (Lv.3) - 문제풀이

유승한·2023년 5월 30일

📝문제

현대자동차그룹은 코딩 테스트를 위한 문제들을 많이 가지고 있는데, 관리를 위해 문제의 난이도를 1레벨에서 N레벨까지 총 N개의 레벨로 구분하고 있다.
문제 중에 난이도가 정확히 i레벨로 평가된 문제는 총 ci개가 있고, 난이도를 정확히 매기기 애매하다는 평가를 받아 난이도를 i레벨또는 i+1레벨로 매길 수 있다고 평가된 문제는 총 di개가 있다.

이외에 다른 문제는 없다. 현호는 현대자동차그룹 채용 시험을 위해 코딩 테스트 세트를 만드는 작업을 하고 있다. 하나의 코딩 테스트 세트는 1에서 N사이의 모든 난이도를 가지는 문제 N개를 모은 것이다.
난이도가 애매한 문제들은 현호가 임의로 가능한 난이도를 적절히 매겨 넣을 때, 서로 같은 문제를 포함하지 않는 코딩 테스트 세트는 최대 몇 개 만들 수 있을까?

여러 ci, di에 대한 시나리오가 T번 주어진다.

📌제약조건

3 ≤ N ≤ 105
3 ≤ N·T ≤ 105
0 ≤ ci, di ≤ 1012

⌨입력형식

첫 번째 줄에 하나의 코딩 테스트 세트가 가지는 난이도의 개수를 나타내는 자연수 N과 시나리오의 개수를 나타내는 자연수 T가 주어진다.
다음 T개의 줄에는 각 줄마다 시나리오가 하나씩 주어진다.

각 시나리오는 문제 개수를 나타내는 2N-1개의 정수 c1, d1, c2, d2, c3, ..., cN-1, dN-1, cN로 이루어져 있다.

💻출력형식

T개의 줄에 걸쳐서, i번째 줄에는 i번째로 주어진 시나리오에 대해 만들 수 있는 코딩 테스트 세트가 최대 몇 개인지 출력한다.

📃입출력예시

입력예제)

3 3 2 2 1 1 3 39 31 97 95 24 1000 1000 1000 1000 1000

출력예제)

3 70 1666

첫 번째 시나리오는 아래와 같은 문제 배정을 통해 최대 3개의 세트를 만들 수 있다.

Case 1
Case 2

※남은 문제 레벨: 1, 3, 3

하지만, Case 2와 같이 문제 배정을 하면 2레벨의 문제를 배정할 수 없으므로, 2개의 세트 밖에 만들지 못한다.
따라서, 첫 번째 시나리오로 만들 수 있는 코딩 테스트 세트는 최대 3세트 이다.

🔑풀이

처음에 코드를 구현해보려고 시도했지만 잘되지 않았다. 그래서 Softeer에서 제공하는 해설 동영상을 참고하여 문제를 해결하였다.

정답을 찾는 과정이 정말 참신했다.
문제의 정답이 존재하는 범위를 사용해서 이진 탐색을 통해 해결할 수 있다는 접근 방식이 놀라웠다.

1. Python Code

# 문제 난이도 1레벨 ~ N레벨 / 난이도의 개수 N개
# 시나리오의 개수 T개
# 하나의 코딩 테스트 세트는 문제 개수를 나타내는 2N-1개의 정수들로 구성되어 있음
# c1, d1, c2, d2, ... cn-1, dn-1, cn
# 하나의 코딩 테스트 세트는 1에서 N사이의 모든 난이도를 가지는 문제 N개를 모은 것

def test(num):
    ptable = [0] * N
    ptable[0] = clist[0]
    for i in range(N-1):
        if ptable[i] >= num:
            ptable[i+1] = clist[i+1] + dlist[i]
        elif ptable[i] + dlist[i] >= num:
            ptable[i+1] = clist[i+1] + (ptable[i] + dlist[i] - num)
        else:
            return False
    if ptable[N-1] >= num:
        return True
    else:
        return False

def BinSearch(start, end):
    if start > end:
        return BinSearch(start-1, end)
    mid = (start + end) // 2
    if test(mid):
        if start == end:
            return start
        else:
            return BinSearch(mid+1, end)
    else:
        return BinSearch(start, mid-1)

N, T = map(int, input().split())

for i in range(T):
    clist = []
    dlist = []
    problems = list(map(int, input().split()))
    for j in range(len(problems)):
        if (j % 2):
            dlist.append(problems[j])
        else:
            clist.append(problems[j])
    print(BinSearch(0, 2*(10**12)))