BOJ 25709번: 1 빼기

문제

---

문제 풀이 - 오답 (맞왜틀?)

1. 덱에 넣기
2. 가장 앞의 수가 1이면 (2) 수행 (front가 0이면 계속 pop_front() 수행)
3. 아니면 가장 1의 자리 수 없애기 (1의 자리 - 1)번 (1) 수행하고 (2) 한번 수행
4. 위 과정을 한 자리 수만 남을 때까지 반복
5. 마지막 수만큼 횟수 증가하고 출력

#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
using namespace std;

deque<int> dq;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int ans = 0;
    string str;
    cin >> str;

    int len = str.length();
    for (int i = 0; i < len; i++) { dq.push_back((int)(str[i] - '0')); }

    while (dq.size() > 1) {
        if (dq.front() == 1) {
            ans++;
            dq.pop_front();
            while (dq.front() == 0 && dq.size() > 1) { dq.pop_front(); }
        }
        else {
            if (dq.back() == 0) {
                ans++;
                for (int i = dq.size() - 1; i >= 0; i--) {
                    if (dq[i] == 0) { dq[i] = 9; }
                    else { dq[i]--; }
                }
            }
            ans += dq.back();
            dq.pop_back();
        }
    }

    ans += dq.back();
    cout << ans;

    return 0;
}

왜 틀렸지 예제는 다 잘 나오는데 틀렸습니다...

---

문제 풀이2 - 맞았습니다!

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int ans = 0, n;
    bool m, flag;
    string str;

    cin >> n;

    while (true) {
        m = true;
        str = to_string(n);

        for (int i = 0; i < str.length(); i++) {
            if (str[i] == '1') { // 숫자 중에 1이 있는 경우
                flag = false;
                string temp = "";
                for (int k = 0; k < str.length(); k++) {
                    if (k == i) { continue; } // 그 1을 빼고 새로운 0을 만들기

                    if (str[k] != '0') { flag = true; } // 숫자 사이에 0이 있는 경우 같이 들어가도록 하기
                    if (flag) { temp += str[k]; }
                }
                str = temp;
                m = false;
                break;
            }
        }
        ans++;

        if (str == "") { break; } // 숫자가 남지 않으면 루프 종료

        n = stoi(str);
        if (m) { n--; }
    }

    cout << ans;

    return 0;
}

다른 풀이를 참조해서 풀었다.