대한민국을 지키는 가장 긴 힘

• 이런 비슷한 유형의 문제들에서 흔히 사용되는 방법은 DP이다. 이 문제도 i번째 숫자에 대해서 가장 적은 병사수를 dp[i]에 저장해두면, dp[n]을 dp[n-1], dp[n-2], dp[n-3]으로부터 계산할 수 있으므로, 기본적인 1차원 DP 문제가 되어서 O(n)에 풀 수 있다.
• 이 문제는 사실 그리디로 풀린다. 앞에서부터 시작해서, 묶을수 있는 최대 개수만큼 숫자들을 묶어서 하나의 수로 만들어가는 과정을 반복해도 최적값을 구할 수 있다. 현재 가능한 최대 개수보다 적은 개수의 숫자를 묶어서 하나의 수를 만들어야만 더 이득이 되는 경우는 존재하지 않는다는 것을 직관적으로 알수 있다.
• 다만 이렇게 그리디를 구현하면 좀 번거롭다. 3개의 숫자를 묶어서 적법한 세자리수를 만들수 있는지 확인하려면, S[i], S[i+1], S[i+2]를 이용해서 만든 세자리수의 크기를 641과 비교하는 것과 덧붙여서, S[i+3]이 0이 아닌지를 함께 체크해야 한다. 대신에 뒤에서부터 묶어가는 식으로 그리디를 접근하면 좀더 구현이 쉬워진다. S[i-2],S[i-1],S[i] 의 세개의 숫자만 갖고 세자리 수를 만들어서, 이 수가 100 이상인지 (0으로 시작하지 않는지) 와 641 이하인지를 같이 체크하면 된다.
  • [추가] 에디토리얼을 보고 깨달았는데, 그냥 정방향으로 그리디를 짜더라도 좀더 간단히 구현할수 있다. 숫자를 나누는 시점에 다음수의 첫자리가 0인지를 확인하는 대신에, 일단 현재 수를 만들때에는 다음수를 신경쓰지 말고 가장 큰 수를 만들어놓고, 다음 수를 만들때 첫자리가 0이면 이전 수에서 마지막 숫자를 빼버리는 식으로 처리하는 방법도 있다.
• DP든 그리디든 시간복잡도는 O(n)으로 동일하다
  • 범위가 작아서, 백트래킹도 가능하다고 한다.

"""Solution code for "BOJ 31263. 대한민국을 지키는 가장 긴 힘".

- Problem link: https://www.acmicpc.net/problem/31263
- Solution link: http://www.teferi.net/ps/problems/boj/31263

Tags: [greedy]
"""


MAX_NUM = 641


def main():
    N = int(input())
    S = input()

    answer = 0
    i = N
    while i > 0:
        answer += 1
        if i > 2 and 100 <= int(S[i - 3 : i]) <= MAX_NUM:
            i -= 3
        elif i > 1 and 10 <= int(S[i - 2 : i]):
            i -= 2
        else:
            i -= 1

    print(answer)


if __name__ == '__main__':
    main()