[알고리즘 문제] 카드 게임 조작 (Python / 파이썬)

문제

유니는 카드 게임을 하고 있다.
이 카드 게임은 N + 1종류의 카드를 사용한다. 각 카드는 0~N의 번호가 적혀 있다.
i가 적힌 카드는 i장 이상의 카드를 사용한 다음에 사용 가능하다. 즉, 0이 적힌 카드는 언제든 사용 가능하고 10이 적힌 카드는 다른 카드를 10장 사용해야 사용 가능하다.
유니는 N번 카드를 갖고 있고, 그 외에도 여러 장의 카드를 갖고 있다. 유니는 N번 카드를 사용하고 싶지만 N장의 다른 카드를 사용해야 N번 카드를 사용할 수 있기 때문에 N번 카드를 사용할 수 없을 수도 있다.
만약 유니가 N번 카드를 사용할 수 없다면 미리 몰래 숨겨둔 카드들을 가져와서 사용하려고 한다. 유니는 철저하기 때문에 0~N번 카드를 모두 N장씩 숨겨뒀다. 따라서 가져올 카드가 부족해서 N번 카드를 못 낼 상황은 존재하지 않는다.
숨겨둔 카드를 너무 많이 가져오면 조작이 들킬 수 있으니 최소한의 카드만 가져와서 N번 카드를 내려고 한다. 유니가 최소 몇 장의 카드를 가져와야 N번 카드를 낼 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트케이스의 수 T가 주어진다..
각 테스트케이스의 첫 줄에 유니가 갖고 있는 0~N번 카드의 수가 공백 없이 주어진다. 만약 2341처럼 주어진다면 0번 카드가 2장, 1번 카드가 3장, 2번 카드가 4장, 3번 카드가 1장이라는 뜻이다.
N번 카드는 항상 한 장 이상 존재한다.
( 1 ≤ T ≤ 10, 1 ≤ N ≤ 1,000 )

출력

각 테스트케이스마다 '#'과 테스트케이스의 번호, 공백을 출력한 뒤 유니가 가져와야 하는 카드의 수를 출력한다.

---

문제 풀이

0~N번까지의 카드가 있을 때 각 카드는 이전에 각 카드 번호 수만큼

카드를 사용했어야 사용 가능합니다. 

 

0번 카드는 항상 사용 가능하므로 먼저 0번 카드의 수를 초기값으로 설정해줍니다.

1번 카드부터 카드를 사용할 수 있는지 확인해줍니다.

만약 지금까지 사용한 카드의 수가 현재 카드 번호보다 크거나 같다면 

현재 카드를 사용 가능하므로 현재 카드의 수를 더해줍니다.

만약 현재 카드를 사용할 수 없다면 카드를 가져와야합니다.

이때, 카드는 한장만 가져오면 됩니다.

왜냐하면 이미 이전 인덱스까지 과정을 완료했다는 것은

최소한 이전 인덱스만큼 카드를 사용했다는 뜻입니다. 

따라서 한장만 가져오면 카드를 사용할 수 있으므로 한장을 더해 카드의 수를 더해줍니다.

그리고 가져온 카드의 수를 세기 위해 get을 1 증가시켜줍니다. 

이 과정을 반복하면 유니가 가져온 카드의 수를 출력할 수 있습니다.

---

My Code

for tc in range(int(input())):
    card = list(map(int,input())) # 유니가 가진 각 카드의 수

    get = 0
    sum_value = card[0] # 0번 카드는 항상 사용 가능
    for i in range(1, len(card)): 
        if sum_value >= i: # i보다 이전에 더 많이 카드를 사용했다면
            sum_value += card[i] # 카드를 사용
        else:              # 카드를 사용할 수 없다면
            sum_value += card[i] + 1 # 한장을 가져와 카드를 사용
            get += 1 # 가져온 카드 수를 세어줌

    print('#' + str(tc + 1), end = ' ')
    print(get)