[Baekjoon 31263] 대한민국을 지키는 가장 긴 힘 | Python

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

---

문제

 

주어진 남은 복무일이 적혀있는 페이퍼를 보고 해당 페이퍼를 작성한 병사 수의 최솟값을 출력하는 문제이다.

병사들의 복무 일수가 641일이기 때문에 남은 복무일 수는 1 이상 641 이하이다.

 

---

풀이

 

전역일 페이퍼에 적혀있는 수는 자르게 되면 1 이상 641 이하이고, 불필요한 0이 없어야 한다.

조건을 생각해본다면 전역일 페이퍼 시작은 0이 아닌 수이고, 0이 세 번 연속 나올 수 없다.

각 복무일을 끊어주면서 가능한지 불가능한지 생각하면서 가능한 남은 복무일이 많이 나오도록 계산한다면 전역일 페이퍼를 적은 최소 인원을 계산할 수 있다. 예를 들어 전역일 페이퍼가 21993 이라면 2일보다 21일이 길고, 21일보다 219일이 기므로 219일을 잘라주고, 전역일 페이퍼를 작성한 병사를 한 명 추가한다. 남은 93 에 대해서도 9일보다 93일이 기므로 또 한 명을 추가한다. 따라서 최솟값은 두 명이다. 물론 각 수가 1 이상 641 이하인지 확인해야 한다.

그런데 특이점은 0 이다. 조건을 생각해본다면 전역일 페이퍼 시작은 0이 아닌 수이고, 0이 세 번 연속 나올 수 없다. 그 외 숫자들은 그 숫자만 보고 전역일을 특정하기 어렵다. 특이점이 0 이므로 0 을 조건으로 가능한지 불가능한지를 먼저 검사할 수 있다. 그리고 0 이 되는지 검사해야 하는 곳은 세 번째 자리이다.

각 남은 복무일의 앞자리가 0 이 아니므로 첫 번째 자리는 무조건 0 이 아닌 숫자이다. 두 번째 자리는 조건을 생각해본다면 두 번째 자리가 0 인지 확인해도 결국 세 번째 자리를 검사해야 한다. 따라서 0 인지 아닌지를 검사하는 의미있는 자리는 세 번째 자리이다.

• 세 번째 자리가 0 인 경우

• 이제 네 번째 자리가 0 인지 확인해야 한다. 만약 네 번째 자리 역시 0 이라면 끊어준 숫자는 ??00이라는 것을 알 수 있다. 그렇다면 ?/?00으로 끊어주어야 한다. 만약 네 번째 자리가 0 이 아닌 숫자라면 끊어준 숫자는 ??0?이다. 이때는 바로 끊어줄 수 없고, ??0이 641을 초과하는지 확인해야 한다. 만약 641을 초과한다면 ?/?0?로 끊어주어야 하고, 초과하지 않는다면 ??0/?로 끊어주어야 한다.

• 세 번째 자리가 0 이 아닌 경우

• 이제 네 번째 자리가 0 인지 확인해야 한다. 만약 네 번째 자리가 0 이라면 끊어준 숫자는 ???0이라는 것을 알 수 있다. 그렇다면 ??/?0으로 끊어주어야 한다. 만약 네 번째 자리가 0 이 아닌 숫자라면 끊어준 숫자는 ????이다. 이때는 바로 끊어줄 수 없고, 앞 세 자리 ???가 641을 초과하는지 확인해야 한다. 만약 641을 초과한다면 ??/??로 끊어주어야 하고, 초과하지 않는다면 ???/?로 끊어주어야 한다.

이러한 과정을 반복하여 전역일 페이퍼를 끊어가며 병사 수를 확인한다면 전역일 페이퍼를 작성한 최소 병사수가 몇 명인지 확인할 수 있다.

단 0 인지 아닌지 확인하면서 인덱싱을 사용하고 페이퍼를 끊어주면서 슬라이싱을 사용하는데 이때 범위를 주의해야 한다. 아래 코드에서는 슬라이싱 값을 따로 설정하고, 0 인지 아닌지 확인하기 전에 범위를 넘는지 확인하는 것으로 오류가 없도록 하였다.

 

---

코드

 

paper_n = int(input())
paper = input()
idx = 0
cnt = 0
while idx < paper_n:
    idx_end = min(idx+3, paper_n)
    if idx + 2 < paper_n and paper[idx+2] == '0':
        if idx + 3 < paper_n and paper[idx+3] == '0':
            idx += 1
            cnt += 1
        elif int(paper[idx: idx_end]) <= 641:
            idx += 3
            cnt += 1
        else:
            idx += 1
            cnt += 1
    else:
        if idx + 3 < paper_n and paper[idx+3] == '0':
            idx += 2
            cnt += 1
        elif int(paper[idx: idx_end]) <= 641:
            idx += 3
            cnt += 1
        else:
            idx += 2
            cnt += 1
print(cnt)