[Python 3] BOJ 30205 전역 임무

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

[30205번: 전역 임무

김 병장이 소속된 특수부대는 전역을 하려면 특이하게 대대장으로부터 주어진 임무를 달성해야 한다. 김 병장이 받은 임무는 적군의 $1$번 기지부터 $N$번 기지까지 모두 순서대로 격파하는 것이

www.acmicpc.net](https://www.acmicpc.net/problem/30205)

이번 문제는 그리디 알고리즘을 이용하여 풀었다.

n,m,p=map(int,input().split())
for i in range(n):
    data=list(map(int,input().split()))
    data.sort()
    minusone=data.count(-1)
    temp=minusone
    for j in data[temp:]:
        if j>p:
            while j>p:
                if minusone>=1:
                    minusone-=1
                    p*=2
                else:
                    print(0)
                    exit(0)
            p+=j
        else:
            p+=j
    while minusone:
        minusone-=1
        p*=2
print(1)

먼저, 각 줄마다 가야할 기지에 대한 정보가 나와있다.
-1은 공격력을 2배로, 나머지 정수들은 지금 현재 내 공격력보다 낮으면 내가 더한다.

그럼 해당 풀이를 최적의 해로 구현하기 위해서는,

*"최대한 싸워볼 적들이랑 싸워보고, 안 될 것 같을 때마다 -1 더블을 하자!"*
이다.

또한 조심해야할 케이스는, 만약 싸울 적은 없고 -1 더블 아이템만 있을 때이다. 이럴 때에는 그냥 더블만 하면 된다.
그리고 만약 적들은 다 물리쳤는데, 더블 아이템이 남아 있으면, 모두 쓰고 가야한다. 다음 기지에 가서 써야할 수도 있기 때문이다.