백준 24595번 Rise and Fall [C++]

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

 

 

#문제 간단 정리

문제는 간단하니 번역은 안달아두겠다

 

대략 같거나 증가하는부분 같거나 감소하는 두 부분으로 이루어진 숫자를 만드는데

주어진 숫자와 같거나 작은수중에서 가장 큰 숫자를 만들면 된다

 

그리디 문제이다

 

 

#문제 해결 방법

 

우선 증가할때는 그대로 놔두는게 최선책이다

 

왜냐하면 앞자리수를 하나 내리게 되면 가장 손실이 크기 때문에

일단 증가하면 그대로 놔두고

 

감소할때가 관건인데 감소할 때 숫자가 작아진다면

계속 작아지게 놔두고

만약 작아지다가 작아진 값보다 큰 값이 나온다면 

그 이전 값으로 전부 통일시켜주면 된다

예를들어서

 

1234543291111

이라면 

123454322222

가 되는거다 왜냐면

91111

보다 

22222

가 작은 수가 되기 때문이다

이 부분에 주의하자

 

 

#전체 코드

#include <iostream>
#include <vector>
#include <unordered_map>
#include <utility>

using namespace std;



int main() {

    int t; cin >> t;

    while (t--) {
        string s;
        cin >> s;

        bool fall = false;
        char fix;
        bool isfix = false;
        for (int i = 1; i < s.length(); i++) {

            if (!fall) {
                if (s[i] - '0' < s[i - 1] - '0') {
                    fall = true;
                    fix = s[i];
                }
            }
            else {

                if (!isfix) {
                    if (s[i] - '0' > s[i - 1] - '0') { //더 커지는 순간 고정
                        s[i] = fix;
                        isfix = true;

                    }
                    else { //더 작아지면
                        //s[i] = s[i - 1];
                        fix = s[i];
                    }
                }
                else {
                    s[i] = fix;
                }

            }
        }

        cout << s << '\n';
    }

    

    return 0;
}