[Softeer] 21년 재직자 대회 본선 - 코딩테스트 세트

문제

<배경>

현대자동차그룹은 코딩 테스트를 위한 문제들을 많이 가지고 있는데, 관리를 위해 문제의 난이도를 $1$레벨에서 $N$레벨까지 $N$레벨로 구분하고 있다.

문제 중에 난이도가 정확히 $i$레벨로 평가된 문제는 총 $c_i$개가 있고, 난이도를 정확히 매기기 애매하다는 평가를 받아 난이도를 $i$레벨 또는 $i+1$레벨로 매길 수 있다고 평가된 문제는 총 $d_i$개가 있다.

이외에 다른 문제는 없다.

 

현호는 현대자동차그룹 채용 시험을 위해 코딩 테스트 세트를 만드는 작업을 하고 있다.

하나의 코딩 테스트 세트는 $1$에서 $N$사이의 모든 난이도를 가지는 문제 $N$개를 모은 것이다.

난이도가 애매한 문제들은 현호가 임의로 가능한 난이도를 적절히 매겨 넣을 때, 같은 문제를 포함하지 않는 코딩 테스트 세트는 최대 몇 개 만들 수 있을까?

여러 $c_i, d_i$에 대한 시나리오가 $T$번 주어진다.

 

<입력>

<출력>

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

---

풀이

이 문제는 이진탐색의 아이디어를 가져와서 풀 수 있다.

0부터 $c_i, d_i$가 각각 최대 $10^{12}$까지 가능하기 때문에 최대치로 만들 수 있는 테스트세트의 개수는 $2\times 10^{12}$가 된다.

따라서 처음 ($0, 2\times 10^{12}$)까지의 범위에서부터 이진탐색을 하며 어떤 특정 테스트세트의 개수만큼 만들 수 있는지 없는지 판단하면 된다.

 

 

먼저 기본 입력을 받는다.

N,T = map(int,input().split())
for i in range(T):
    C = [0] * N
    D = [0] * N
    Temp = list(map(int,input().split()))
    for i in range(N-1):
        C[i] = Temp[2*i]
        D[i] = Temp[2*i+1]
    C[N-1] = Temp[2*(N-1)] 
    print(bSearch(0, 2*10**12))

 

test라는 함수는 주어진 문제상황에서 인자로 들어온 testSets개 만큼의 세트를 만들 수 있는지 없는지 판단한다.

이 판단 여부에 따라 이진탐색의 범위를 나눠 최대로 만들 수 있는 세트 수를 찾는 방식이다.

S[i]는 c[i]의 값에 혹시나 남았을 D[i-1]을 더한 값이다.

이해가 잘 안갈 수 있지만 아래 여러 경우로 나눠서 이해를 하다보면 S의 의미를 알게 될 것이다.

 

i+1 단계에 사용할 수 있는 문제 개수를 따져보자.

Case1 : 먼저 i단계 문제를 D[i]의 문제를 하나도 사용하지 않고도 개수를 충족 시킬 수 있다면 D[i]의 문제는 모두 i+1단계로 설정해서 배정해줄 수 있다.

Case2 : 이번엔 자체적으로 개수를 채울 수는 없지만 D[i]의 문제 일부를 i단계로 설정하면 해당하는 테스트세트 개수를 충족시킬 수 있다면, i+1단계에 사용할 수 있는 문제는 기본 C[i+1]개 문제에 앞에서 쓰고 남은 문제만큼을 더 쓸 수 있는 것이다.

Case3 : 만약 D[i]의 문제를 모두 i단계로 배정해도 i단계의 개수를 만족 시킬 수 없다면 여기서 끝난다.

def test(testSets):
    S = [0]*N
    S[0] = C[0]
    for i in range(N-1):
        if S[i] > testSets: #case1
            S[i+1] = C[i+1] + D[i]
        elif S[i] + D[i] >= testSets: #case2
            S[i+1] = C[i+1] + (S[i] + D[i] - testSets)
        else: #case3
            return False
    if S[N-1] >= testSets:
        return True
    else:
        return False

 

그리고 일반적인 이진탐색 함수이다.

mid를 구할 때 +1이 되어있다는 점이 약간 다르고 그 외는 일반적인 함수와 똑같다.

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