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

문제 링크 : https://softeer.ai/practice/info.do?idx=1&eid=630

Softeer

정답 코드

import sys
input = sys.stdin.readline
N, T = map(int, input().split())

def check(value):
    now = confirmed_level[0]
    for idx in range(N-1):
        if now >= value:
            now = confirmed_level[idx+1] + neutral_level[idx]
        elif now + neutral_level[idx] >= value:
            now = confirmed_level[idx+1] + (now + neutral_level[idx] - value)
        else:
            return False
            
    if now >= value:
        return True
    else:
        return False

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

for tc in range(T):
    confirmed_level = [0 for _ in range(N)]
    neutral_level = [0 for _ in range(N-1)]
    scenario = list(map(int, input().split()))
    for idx in range(N-1):
        confirmed_level[idx] = scenario[2*idx]
        neutral_level[idx] = scenario[2*idx + 1]
    confirmed_level[N-1] = scenario[-1]
    print(binarySearch(0, 2*10**12))

어려운점

1. 이진법에 대해서 먼저 떠오르긴 했다. 하지만 start값과 end값을 어떻게 설정할지 고민이었다.

2. 이진탐색에 check라는 함수를 또 만들어야 했는데 아직 이해가 제대로 되지 않았다.

 

느낀점

- 무조건 다시 풀어보고 이진탐색에 대해 공부해야겠다.