그리디-대한민국을 지키는 가장 긴 힘

https://www.acmicpc.net/problem/31263
백준 31263번 대한민국을 지키는 가장 긴 힘

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 1024 MB 780 268 218 41.366%
문제
대한민국 공군의 표어는 "대한민국을 지키는 가장 높은 힘"이다. 하지만, 복무 일수가
$1$년
$9$개월로 현역 복무 병사들 중 가장 길다는 이유로 공군 병사들은 자조적으로 "대한민국을 지키는 가장 긴 힘"이라는 농담을 주고받곤 한다.

오늘도 "대한민국을 지키는 가장 긴 힘"이라는 농담을 주고받던 도훈이네 부대 병사들은 전역의 염원을 담은 전역일 페이퍼를 만들기로 결심했다. 전역일 페이퍼란, 긴 종이에 병사들의 남은 복무 일수를 띄어쓰기 없이 한 줄로 나열하는 것이다. 가령, 남은 복무 일수가 각각
$124$일,
$631$일,
$2$일 남은 병사들이 순서대로 전역일 페이퍼를 작성하면, 종이에는
$1\,246\,312$라는 수가 적히는 것이다. 공군의 최대 복무 일수는
$641$일이기 때문에, 전역일 페이퍼에 본인의 남은 전역일을 작성한 사람들은 모두
$1$ 이상
$641$ 이하의 수만을 작성하였으며, 수 앞에 불필요한
$0$을 붙이지 않았다고 한다.

이렇게 만든 전역일 페이퍼를 보던 도훈이는, 문득 해당 전역일 페이퍼에 본인의 남은 복무 일수를 작성한 병사의 수가 몇 명인지 알고 싶어졌다. 다만, 전역일 페이퍼에 적힌 수만 보고서는 정확한 인원수를 알 수 없었기에, 각 병사가 가능한 남은 복무 일수인
$1$ 이상
$641$ 이하의 수만을 작성했다는 사실을 토대로 전역일 페이퍼를 작성한 병사 수의 최솟값을 구하기로 했다. 도훈이를 위해 전역일 페이퍼를 작성한 병사 수의 최솟값을 구해주자!

입력
첫 번째 줄에 전역일 페이퍼에 적힌 수의 자릿수
$N$이 주어진다.

두 번째 줄에 전역일 페이퍼에 적힌 수를 나타내는 길이
$N$의 정수
$S$가 주어진다.

주어진 수
$S$가 전역일 페이퍼에 적힌 수가 될 수 있음이 보장된다.

출력
첫 번째 줄에 전역일 페이퍼를 작성한 병사 수의 최솟값을 출력한다.

공군 boj 대회인 보라메 컵에서 열린 대회 문제이다.(공군출신 피셜)
실버3치고는 상당히 고민할거리도 많고 나도 삽질을 좀 많이 했다.

이 문제를 풀때 가장 중요한 점은 숫자를 몇개단위로 잘라서 판단할것인가?이다.

내가 기존에 풀었던 틀린코드를 보자.

N = int(input())
lst = list(map(int, input().strip()))

ans = 0
cal = 0

for i in lst:
    if i == 0:
        if cal * 10 + i > 641:
            ans += 2
            cal = 0
        else:
            cal = cal * 10
    else:
        if cal * 10 + i > 641:
            ans += 1
            cal = i
        else:
            cal = cal * 10 + i

if cal != 0:
    ans += 1

print(ans)

간단하게 다음 숫자 1개만 보고 판단해서 말 그대로 '그리디'스럽게 풀었다.
하지만 이렇게 푼다면 00이 붙은 경우 어떻게 처리해야되는가? 라는 의문이 든다.

하지만 저렇게 푼 이유는 백준 사이트에 있는 모든 예제가 통과한다는 것이다.
반례를 보도록 하자.

input = 23401 일 경우의 반례이다.
원래대로라면 cal이 절대 0이 나올수가 없다.
왜냐? 23/401/1 로 잘려야 하기 때문에 0이 단독으로 나온다면
그것은 잘못된 계산이라는 것이다.

그래서 갈아엎었다.

N = int(input())
lst = list(map(str, input().strip()))

ans = 0
cal = 0

while lst:
    if len(lst) <= 3:
        if int(''.join(lst[:3])) <= 641:
            ans += 1
            break
        else:
            lst = lst[2:]
            ans += 1
    else:
        if lst[2] == '0':
            
            if lst[3] == '0':
                lst = lst[1:]
                ans += 1
            else:
                if int(''.join(lst[:3])) <= 641:
                    lst = lst[3:]
                    ans += 1
                else:
                    lst = lst[1:]
                    ans += 1

        else:
            if lst[3] == '0':
                lst = lst[2:]
                ans += 1
            else:
                if int(''.join(lst[:3])) <= 641:
                    lst = lst[3:]
                    ans += 1
                else:
                    lst = lst[2:]
                    ans += 1
         
print(ans)

상당히 지저분하고 복잡한 코드가 되었는데, 핵심은 다음과 같다.

• 리스트를 3개씩 나눠서 판별한다.
• 이때, 끝지점에 0이 어떻게 들어갔냐를 판별한다.
• 즉, lst[2], lst[3]에 0이 들어있냐/없냐에 따라 경우의 수를 나눈다.

문제의 정의를 잘 보고 정확하고 깔끔하게 풀어야 한다.

백준 랭킹 3프로 안에 들어갔다.
요즘 이거 보는맛에 산다.