import sys
input=sys.stdin.readline
N,ATK=map(int,input().split())
L=[]
for i in range(N):
t,a,h=map(int,input().split())
L.append([t,a,h])
start=1
end=100000000000000000
HP=0
#내 HP- ( (상대 HP//내 공격력)-1)*상대공격력
while start<=end:
H_ATK=ATK #while 문 안에서 변동하는 ATK 변수
mid=(start+end)//2
HP=mid
count=0 #던전 탐험에 성공했는지 확인해주는 변수
for i in range(N):
if L[i][0]==1:
if L[i][2]%H_ATK==0:
if HP-( (L[i][2]//H_ATK)-1)*L[i][1]>0:
HP-=( (L[i][2]//H_ATK)-1)*L[i][1]
else:
count=1
break
elif L[i][2]%H_ATK!=0:
if HP-( (L[i][2]//H_ATK))*L[i][1]>0:
HP-=( (L[i][2]//H_ATK))*L[i][1]
else:
count=1
break
elif L[i][0]==2:
H_ATK+=L[i][1]
if L[i][2]+HP>mid:
HP=mid
else:
HP+=L[i][2]
if count==1:
start=mid+1
else:
end=mid-1
print(start)📌 어떻게 문제에 접근할 것인가?
문제자체는 길어보이지만 내용은 쉽다.
초기 용사의 공격력과 던전의 수가 주어졌을때 턴제게임처럼 용사가 먼저 때린 후 , 몬스터가 용사를 때린다.
그리고 체력이 먼저 0 이 되는사림이 진다. 이때 던전을 깰수있는 최소 HP 를 구하는 것이다.
하지만 하나같이 문제에서 주어지는 변수의 범위가 괴랄하다.
N(1≤N≤123456)|HATK(1≤HATK≤1,000,000)|ti,ai,hi(ti∈{1,2},1≤ai,hi≤1000000)
범위가 크지만 가장 문제되는 점은 N 의 범위이다.
안그래도 최소 HP를 구해야 하는데 반복횟수도 100000 이 넘어가니 완전탐색과 같은 알고리즘은 쓰기가 매우 까다롭다.
따라서 이분탐색 을 통해 문제를 풀어보고자 한다.
📌 어떻게 이분탐색을 할것인가?
이분탐색에서 mid 값은 체력 값을 의미한다. 그리고 매번 mid 값을 설정해 준후 던전에 들어가서 싸워서 이길수 있는지 없는지 판단한다.
턴제게임에서 만약 상대방의 HP 를 내 공격력으로 나누었을때 나머지가 0 이라면
내 HP- ( (상대 HP//내 공격력)-1)*상대공격력 이라는 공식이 성립하고
나머지가 0 이 아닐때는 내 HP- (상대 HP//내 공격력)*상대공격력 이 성립한다.
이 부분은 몬스터의 공격력과 체력을 임의로 지정해주면서 직접 시뮬레이션을 해보는것을 추천한다.
이후 몬스터와 싸웠을때 체력이 0 보다 크면 다음 던전을 들어가고 0 이하가 되면 죽었으므로 break 해준다.
참고로 end 값은 무조건 100000000000000000 이상으로 잡아야한다. 그렇지 않을 경우 제대로 코드를 작성하여도 70% 쯤에서 틀렸다고 나온다.
end 값을 줄이자니 틀렸다고 나오고 증가하자니 시간초과가 뜨기 때문에 end값을 찾는 것도 매번 제출하면서 확인해야한다.
그리고 python 으로 제출하면 시간초과로 거의 불가능하기때문에 꼭 pypy3로 제출하자.
✅ 코드에서 중요한 부분
end=100000000000000000으로 잡아준다.- 상대
HP를 내 공격력으로 나눴을때 나머지가 있느냐 없느냐에 따라 깍이는 체력이 달라진다. - 체력포션을 먹을때 처음 체력보다 많아지면 처음 체력으로 되돌아간다.
- 이분탐색이지만 리스트는 정렬해서는 안된다. 던전에 순서가 정해져있기 때문이다.
