(백준) 20008번: 몬스터를 처치하자! 상세 풀이

<포스팅 요약>

1. 문제풀러가기

2. 문제 해결 코드

3. 로직 분석

---

1. 문제풀러가기

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

20008번: 몬스터를 처치하자!

 

문제 해석:

몬스터를 처치하는 최소 시간 출력해주기.

---

2. 문제 해결 코드

코드 (성공) 주석X

from itertools import permutations

n, hp = map(int, input().split())  

def time_memo(time, damage, damage_memo_lst):
    global limit
    idx = 0
    while idx < limit:
        if damage_memo_lst[idx] != 0:
            idx += 1
            continue
        damage_memo_lst[idx] = damage
        idx += time
    return damage_memo_lst

def time_cnt(damage_memo_lst, hp):
    cnt = 0
    for i in range(len(damage_memo_lst)):
        if hp <= 0:
            break
        hp -= damage_memo_lst[i]
        cnt += 1
    return cnt


total_time = 0
total_damage = 0
lst_t_d = []

for i in range(n):
    time, damage = map(int, input().split())
    total_time += time
    total_damage += damage
    lst_t_d.append((time, damage))


limit = total_time*((hp//total_damage)+1)
lst = list(permutations(lst_t_d, n))
result = 1e10

for i in range(len(lst)):
    damage_memo_lst = [0 for _ in range(total_time*((hp//total_damage)+1))]
    for t, d in lst[i]:
        damage_memo_lst = time_memo(t, d, damage_memo_lst)
    result = min(result, time_cnt(damage_memo_lst, hp))
    


print(result)

 

코드 상세 주석

from itertools import permutations

n, hp = map(int, input().split())  # n: 스킬개수 hp:몬스터 hp

# <time_memo 함수 >
# 대기시간 끝날때마다 스킬 사용해주는 함수 구현.
# damage_memo_lst리스트 안에는 스킬을 사용했을시 발생하는 데미지가 들어감

# <time_memo 함수의 로직 상세설명>
# 만약 time_memo(3, 10000, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) 일 때,
# 3초마다 스킬을 사용하므로 => [10000, 0, 0, 10000, 0, 0, 10000, 0, 0, 10000, 0, 0, 10000, 0, 0, 10000, 0]
# 그 다음 time_memo(5, 10001,[10000, 0, 0, 10000, 0, 0, 10000, 0, 0, 10000, 0, 0, 10000, 0, 0, 10000, 0])
# 일 때, if damage_memo_lst[idx] != 0, 즉, 스킬을 동시에 사용하지 못하므로,
# 다른 스킬을 사용했으면 한 칸 건너뛰고(idx+1을 해주고) 그 다음칸부터 대기시간이 발생한다.
# 위 원리로 동작하면 만들어지는 리스트는 => [10000, 10001, 0, 10000, 0, 0, 10000, 10001, 0, 10000, 0, 0, 10000, 10001, 0, 10000, 0]


def time_memo(time, damage, damage_memo_lst):
    global limit
    idx = 0
    while idx < limit:
        if damage_memo_lst[idx] != 0:
            idx += 1
            continue
        damage_memo_lst[idx] = damage
        idx += time
    return damage_memo_lst

# time_memo함수에서 만들어진 리스트로 몬스터가 처치되는 시간을 구한다.
# 몬스터 hp = 70000
# damage_memo_lst=[10000, 10001, 0, 10000, 0, 0, 10000, 10001, 0, 10000, 0, 0, 10000, 10001, 0, 10000, 0]일 때,
# damage_memo_lst[12] 일 때 데미지가 70000이 딱 넘으므로, cnt=12를 리턴


def time_cnt(damage_memo_lst, hp):
    cnt = 0
    for i in range(len(damage_memo_lst)):
        if hp <= 0:
            break
        hp -= damage_memo_lst[i]
        cnt += 1
    return cnt


total_time = 0
total_damage = 0
lst_t_d = []


for i in range(n):
    time, damage = map(int, input().split())
    total_time += time
    total_damage += damage
    lst_t_d.append((time, damage))

# limit은, 몬스터를 처치하는데 아무리 많은 시간을 써봤자 limit시간은 넘기지 못한다.
# 만약 스킬1(3,10000),스킬2(5,10001) 일때, 3+5=8초, 10000+10001=20002데미지라고 하자,
# 8초에 한번 20002 데미지를 입힌다고 계산했을때, 몬스터 hp가 70000이면,
# 70000//20002 = 3이므로 4번만에 처치할 수 있다. 4*8=32이므로 32초만에 처치가능하다.

# 하지만 8초는 넉넉하게 하기위해서 설정한 변수이고, 사실 8초안에 스킬1은 3번쓸 수 있고, 스킬 2는 2번이나 쓸 수 있다.
# 그렇기 때문에 32초는 절대 넘기지 않기 때문에  total_time*((hp//total_damage)+1) 을 limit으로 설정해 둔다.
limit = total_time*((hp//total_damage)+1)
# 스킬1을 먼저 쓸 경우와 스킬 2를 먼저 쓸 경우의 수를 리스트형식으로 출력한다.
lst = list(permutations(lst_t_d, n))
result = 1e10

for i in range(len(lst)):
    # damage_memo_lst리스트를 초기화한다.
    damage_memo_lst = [0 for _ in range(total_time*((hp//total_damage)+1))]
    for t, d in lst[i]:
        # 스킬 대기시간, 데미지, 그리고 damage_memo_lst리스트를 담는다.
        damage_memo_lst = time_memo(t, d, damage_memo_lst)
    result = min(result, time_cnt(damage_memo_lst, hp))
    # 몬스터를 처치하는데 걸린 시간을 출력하고, result와 비교했을때 더 작은수를 result변수에 담아준다.


print(result)

 

---

3. 로직분석

** 만약 스킬이 두개가 있고, 하나는 대기시간이 3초, 데미지는 10000이고, 다른 하나는 5초 데미지는 10001이라고 할 때,

(3,10000),(5,10001) 이라고 표현하겠다. 

1. permutations 외장함수를 사용하여, 스킬 사용 순서의 경우의 수들을 구해준다.

> 경우의 수 :  [((3,10000),(5,10001)),((5,10001),(3,10000))] 

- 그러면 경우의 수는 [((3,10000),(5,10001)),((5,10001),(3,10000))] 이렇게 두개가 있다.

- 경우의 수 1: 대기시간이 3초인 스킬이 먼저 사용될 경우.

- 경우의 수 2: 대기시간이 5초인 스킬이 먼저 사용될 경우.

 

2. 모든 경우의 수를 time_memo함수에 넣어 실행시킨다.

(time_memo는 스킬이 사용될 때마다 데미지값을 넣은 리스트를 출력해주는 함수)

> [10000, 10001, 0, 10000, 0, 0, 10000, 10001, 0, 10000, 0, 0, 10000, 10001, 0, 10000, 0]

<time_memo 함수 로직>

- ((3,10000),(5,10001)) 인 경우부터 돌리면 아래와 같은 로직으로 동작한다. 

> time_memo(3, 10000, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) 실행,
3초마다 스킬을 사용하므로 => [10000, 0, 0, 10000, 0, 0, 10000, 0, 0, 10000, 0, 0, 10000, 0, 0, 10000, 0]

> 그 다음 time_memo(5, 10001,[10000, 0, 0, 10000, 0, 0, 10000, 0, 0, 10000, 0, 0, 10000, 0, 0, 10000, 0]) 실행

if damage_memo_lst[idx] != 0, 즉, 이미 해당 인덱스에 데미지 값이 들어 있다면, 다른 스킬을 사용하고 있는 것이므로,

스킬은 동시에 사용하지 못하기 때문에 한 칸 건너뛰고(idx+1을 해주고) 그 다음칸부터 대기시간이 발생한다.

> 위 원리로 동작했을시 최종적으로 만들어지는 리스트는 => [10000, 10001, 0, 10000, 0, 0, 10000, 10001, 0, 10000, 0, 0, 10000, 10001, 0, 10000, 0]

 

3. 위에서 얻은 리스트를 time_cnt함수에 넣어 실행시킨다.

(time_cnt는 몬스터 처치하는데 걸리는 시간을 출력해주는 함수.)

<time_cnt 함수 로직>

-몬스터 hp = 70000일 때,

- [10000, 10001, 0, 10000, 0, 0, 10000, 10001, 0, 10000, 0, 0, 10000, 10001, 0, 10000, 0]을 해당 함수에 넣으면, cnt=12일 경우 몬스터를 처치할 수 있다.

- 12를 리턴해줌.