BOJ 31263 - 대한민국을 지키는 가장 긴 힘 (C++)

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

문제를 푼 날짜: 25. 05. 27.

#greedy

아이디어

• 꽤 오래 고민한 문제였지만 쉽지 않아 Editorial 및 GPT의 도움을 받았다.
• 병사의 수를 최소화해야 하므로, 왼쪽부터 탐색하며 가능한 한 긴 유효 조각(최대 3자리)을 만든다.
• 현재 위치(pos)에서 3자리까지 조각을 시도하며, 유효하지 않으면 길이를 줄인다.
  • 유효 조건: 조각은 0으로 시작하지 않고, 정수 값이 1 이상 641 이하.
  • 0으로는 시작할 수 없으므로 이전 유효 조각의 마지막 숫자로 현재 위치(pos)를 이동 (이전 유효조각은 길이가 1만큼 줄어도 여전히 유효)
• 가장 긴 유효 조각을 찾으면 그만큼 이동(pos += len), 병사 수 +1
• 이를 문자열 끝까지 반복하여 총 병사 수를 구한다.

Pseudocode (Greedy)

pos ← 0
cnt ← 0
n ← |s|   # 문자열 길이

while pos < n do
    cnt ← cnt + 1
    len ← min(3, n − pos)

    loop  # 이 안에서 “한 조각”을 확정할 때까지 반복
        # 1) 새 조각이 '0'으로 시작하면 → 잘못 끊어진 경계이므로
        if s[pos] == '0' then
            pos ← pos − 1
            len ← min(3, n − pos)
            continue    # 다시 같은 조각에서 재시도
        end if

        # 2) s[pos..pos+len−1] 을 숫자로 변환
        num ← 0
        for i in 0 … len−1 do
            num ← num * 10 + (s[pos+i] − '0')
        end for

        # 3) 1 ≤ num ≤ 641 이면 이 길이로 확정하고 다음 조각으로
        if num ≤ 641 then
            pos ← pos + len
            break      # while‐loop 빠져나가서 다음 조각 시작
        else
            len ← len − 1  # 너무 크면 한 글자 줄여 다시 검사
        end if
    end loop
end while

print cnt

C++ 풀이 (Greedy)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    
    string s;
    cin >> s;

    int pos = 0;
    int cnt = 0;
    

    
    while(pos < int(s.length())){
        cnt++;
        int len = min(3, N - pos);

        while(1){
            int num = s[pos] - '0';
            if(num == 0){
                pos--;
                len = min(3, N - pos);
                continue;
            }

            for(int i = pos + 1; i < pos + len; i++){
                num = num * 10 + (s[i] - '0');
            }

            if(num <= 641){
                pos += len;
                break;
            } else len--;
        }
    }

    cout << cnt;
    return 0;
}