[테스트케이스 추가] 백준 16434번: 드래곤 앤 던전 시간초과 해결 python, 파이썬

1. 문제

https://www.acmicpc.net/problem/16434

16434번: 드래곤 앤 던전

 

 

2. 풀이

binary search + 간단한 simulation

 

이 문제 풀면서 시간초과가 계속 났는데, 용이랑 싸우는 부분에서 직접 구현하면(아래 주석된 부분) 시간 초과가 난다.

수학적으로 해석해서 적어야 한다. 또 play 함수로 만들어서 return 하게 구현했는데 이 부분도 시간초과에 영향을 줬는 지는 조금 더 실험해볼 필요가 있다.

 

시간초과 해결은 이 분의 코드를 참고했다. 👍

 

 

 

3. 구현

import sys
import math
import copy
# sys.stdin=open('input.txt')
sys.setrecursionlimit(10**8)

n, atk = map(int, sys.stdin.readline().split())

lis=[]
while n:
    n-=1
    [t,a,h] = map(int, sys.stdin.readline().split())
    lis.append([t,a,h])

def play(atk, hp):
    max_hp=hp
    cur_atk = atk
    for item in lis:
        # print(item, "hp: ", hp, cur_atk)
        cur_item = copy.deepcopy(item)
        if cur_item[0]==1: # dragon
            # while True:
            #     # print("fight: " ,hp, cur_item[2])
            #     cur_item[2]-=cur_atk
            #     if cur_item[2]<1:
            #         break
            #     hp-=cur_item[1]
            #     if hp<1:
            #         return hp
            hp-=((math.ceil(cur_item[2]/cur_atk)-1)*cur_item[1])
            if hp<1:
                return hp
        else: # portion
            cur_atk+=item[1]
            hp=min(hp+item[2], max_hp)
    
    return hp

le = 1
ri = 10**18

while le<=ri:
    mid=(le+ri)//2
    # res = play(atk, mid)
    cur_hp, cur_atk = mid, atk
    # print(mid, res)
    for item in lis:
        t,a,h = item[0], item[1], item[2]
        if t==1:
            cur_hp-=(math.ceil(h/cur_atk)-1)*a
            if cur_hp<1:
                break
        else:
            cur_atk+=a
            cur_hp=min(cur_hp+item[2], mid)
    if cur_hp<1:
        le=mid+1
    else:
        ri=mid-1
print(le)

 

 

 

4. 반례 + 테케추가

@jeongbeen 님

3 3
1 1 49
2 3 1
1 3 100

답: 64

 

@seico75   님

8 3 
1 1 31
1 1 31
1 1 31
1 1 31
1 1 31
1 1 31
2 3 70
1 3 100

답: 61

 

 

---추가 테케---

5 8
1 1 20
1 3 10
1 3 100
2 5 20
1 3 10

답: 42

 

5 3 
1 1 31
2 1 31
1 1 1
2 3 70
1 3 48

답: 19