log 2020-01-05

---

할 일

• 현장실습 - 과제작업
  • vuex 연동 - 리스트 보여주기
  • (+) 기능 정의서 작성
• 알고리즘 문제풀이
• backlog 만들기

현장실습 - 과제작업

https://www.notion.so/2020-ce018930754848d6a71531bb8c0949a6

backlog 만들기

과제를 위한 backlog?? 필요

알고리즘 문제풀이

백준 16434 - 드래곤 앤 던전

방의 개수 N ~ 123456 초기 공격력 Hatk ~ 1000000 ti, ai, hi (ti ∈ {1, 2}, 1 ≤ ai, hi ≤ 1,000,000)

ti가 1이면 적의 공격력 ai, 체력 hi 2이면 공격력 ai, 체력 hi 올려주는 포션

피를 1 남기고 이기도록.

어려운 점은, 최소의 maxhp를 찾는데 만약 포션이 없다면 피가 줄기만 하므로 적의 공격 총합만 계산하면 된다. 그런데 그렇지 않고 포션으로 자신의 공격력 및 체력이 오르기 때문에 어떤 식으로 해야할지 모르겠다. 체력 증가가 아주 예전에 걸렸던 캡에까지 영향을 줄 수 있기 때문에 그 부분부터 다시 보려면 시간이 오래 걸릴 수 있다. 그런데, 아무리 최대 체력을 증가시켜도, 절대적 체력을 생각해보면, 초기 최대 체력보다 증가하는 경우 그 구간은 어차피 캡에 걸리게 된다. 그렇다면 이제 신경쓸 부분은 그 이후이다. 그 이후에 죽는다면 죽지 않게만 캡을 늘리면 된다.

• 피가 캡에 걸렸다는 것은, 이전 피보다 해당 구간까지 지나는데 피가 증가했다는 것. 따라서 체력을 너무 적게 설정하지 않는 이상 해당 구간에서는 죽지 않는다.
• 그렇다면 각 cappos에 대해, 다음 cappos까지 살아남을 수 있는 최소 최대 체력을 구하고, 그 중 최대를 취한다면? 다음 cappos가 없는 경우 피 1을 남기도록.

py solution

결국 풀었다. 피를 무한이라 생각하고 최소값이 최대값과 비교하여 얼마나 떨어졌는지 알면 끝이었다.

def solve():
    import math
    # it('start')
    n, atk = ria()
    cur = 1000000000000
    maxv = cur
    lastcappos = -1
    minv = cur
    for i in range(n):
        t, a, h = ria()
        if(t == 1):
            turns = math.ceil(h/atk)
            hits = turns-1
            cur -= hits*a
            it(a, h, turns)
            minv = min(minv, cur)
        else:
            it(a, h)
            cur += h
            if(cur > maxv):
                cur = maxv
            atk += a
    it(maxv - minv + 1)

    # WRONG:

    # for i in range(n):
    #     t, a, h = ria()
    #     # it(t, a, h)
    #     # it('turn start. ', i, myhp, atk, t, a, h)
    #     if(t == 1):
    #         it('myhp', myhp)
    #         turns = math.ceil(h/atk)
    #         deathTurns = math.ceil(myhp/a)
    #         it('turns', turns)
    #         it('death', deathTurns)
    #         if(deathTurns < turns):
    #             myhp += (turns-deathTurns)*a
    #             hmax += (turns-deathTurns)*a
    #             deathTurns = math.ceil(myhp/a)
    #             it('newdeath', deathTurns)

    #             myhp = myhp - a*(deathTurns-1)
    #             it('left', myhp)
    #             if(myhp <= 0):
    #                 hmax += 1-myhp
    #                 myhp = 1
    #         else:
    #             myhp = myhp - a*(turns-1)
    #             it('left', myhp)
    #             if(myhp <= 0):
    #                 hmax += 1-myhp
    #                 myhp = 1
    #     else:
    #         myhp += h
    #         if(myhp > hmax):
    #             myhp = hmax
    #             lastcappos = i
    #         atk += a
    #         pass
    #     # it('turn end. ', i, myhp, atk)
    #     pass
    print(int(maxv-minv+1))
    pass

---