이번 문제는 이분탐색을 이용하여 해결하였다. 접근 방식은 다음과 같다.

• 이분탐색에 사용할 left, right를 0과 2e17로 지정한다.
• mid값을 구하고, mid값을 최대hp로 하는 함수를 호출한다.
• 함수의 반환값이 0 이하일 경우에는 최대hp가 부족한 경우이므로, left를 mid+1로 갱신해준다.
• 함수의 반환값이 0 초과일 경우에는 모든 방을 방문했을 때 현재 최대hp가 충분한 것이므로 right를 mid로 갱신한다. 이때 결과변수 answer를 right로 갱신시켜준다. (가능한 경우이므로)

이 과정을 while문을 거치며 계속 반복하면 원하는 결과를 얻을 수 있다. 파이썬의 경우 2e17을 사용하면 float형으로 호출되기 때문에 int형으로 변환하여 진행하였다.

Code

n, ha=map(int, input().split())
rooms=[list(map(int, input().split())) for _ in range(n)]
def visit(hp, mx_hp, ha):
    for i in range(n):
        if rooms[i][0]==1:
            if rooms[i][2]%ha:
                hp-=(rooms[i][2]//ha)*rooms[i][1]
            else:
                hp-=((rooms[i][2]//ha)-1)*rooms[i][1]
        elif rooms[i][0]==2:
            hp=min(hp+rooms[i][2], mx_hp)
            ha+=rooms[i][1]
        if hp<=0:
            break
    return hp
answer=0
left, right=0, int(2e17)
while left<right:
    mid=(left+right)//2
    tmp=visit(mid, mid, ha)
    if tmp<=0:
        left=mid+1
    else:
        answer=mid
        right=mid
print(answer)