대한민국을 지키는 가장 긴 힘 (백준 31263)

안녕하세요. 오늘은 대한민국을 지킬거예요.

문제

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

아이디어

현재 위치에서 최대한 많이 가져가야합니다.
하지만 남은 수가 0으로 시작하면 안됩니다.

이때 최대한 많이 가져가는게 이득인것을 증명해봅시다.
만약 3개를 가져가는것보다 2개를 가져가는것이 이득이라고 합시다.
그러면 2개에서 특정한 개수 x(x=1,2,3)개를 가져가는것이 가장 이득이 됩니다. 하지만 이는 3개를 가져간 상태에서 x-1개를 가져가는것과 동치이므로 이왕이면 3개를 가져가는것이 이득인 것입니다.

소스코드

#include <iostream>
#include <string>
#define ll long long
using namespace std;

bool able(string s)
{
    ll num = 0;
    for (char c : s)
    {
        num *= 10;
        num += c - '0';
    }
    if (num <= 641) return true;
    return false;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, cnt = 0;
    string s;

    cin >> N >> s;
    for (i = 0; i < N; i++)
    {
        if ((i + 3 == N || (i + 3 < N && s[i + 3] != '0')) && able(s.substr(i, 3))) i += 2;
        else if ((i + 2 == N || (i + 2 < N && s[i + 2] != '0')) && able(s.substr(i, 2))) i += 1;
        cnt++;
    }
    cout << cnt;
}

감사합니다.