백준 2529번 부등호

문제 링크입니다: https://www.acmicpc.net/problem/2529

순열을 이용하는 그리디(greedy) 알고리즘 문제였습니다.

알고리즘은 아래와 같습니다.

1. 그리디하게 접근했을 때 최대 숫자는 9 ~ (9 - K)의 숫자들로 이루어질 것이고 최소 숫자는 0 ~ K까지의 숫자들로 이루어질 것입니다.

2. 초기에는 최대 숫자를 내림차순으로 벡터에 저장하고 최소 숫자를 오름차순으로 벡터에 저장한다.

3. 2 번에서 구한 벡터들에 대해 반복문을 돌리는데 저장된 숫자들의 위치와 부등호 간에 모순이 없을 때까지 반복한다.

i) 최대 숫자에 대해 모순이 발생하면 prev_permutation 함수를 이용하여 해당 숫자보다 작으면서 최대인 숫자로 바꿔준다.

ii) 최소 숫자에 대해 모순이 발생하면 next_permutation 함수를 이용하여 해당 숫자보다 크면서 최소인 숫자로 바꿔준다.

4. 3번에서 구한 최대 숫자와 최소 숫자를 출력해준다.

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

 

int K;

vector<int> maxNum, minNum;

string sign;

 

//부등호가 성립하는지 확인

bool valid(vector<int> &v)

{

        //모순을 찾는다

        for (int i = 0; i < sign.length(); i++)

                 if (sign[i] == '<' && v[i] > v[i + 1])

                         return false;

                 else if (sign[i] == '>' && v[i] < v[i + 1])

                         return false;

        //모순이 없을 경우

        return true;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> K;

 

        for (int i = 0; i < K; i++)

        {

                 char temp;

                 cin >> temp;

                

                 sign += temp;

        }

 

        //최대

        for (int i = 9; i > 9 - (K + 1); i--)

                 maxNum.push_back(i);

        while (1)

        {

                 if (valid(maxNum))

                         break;

                 prev_permutation(maxNum.begin(), maxNum.end());

        }

 

        //최소

        for (int i = 0; i < (K + 1); i++)

                 minNum.push_back(i);

        while (1)

        {

                 if (valid(minNum))

                         break;

                 next_permutation(minNum.begin(), minNum.end());

        }

                

        for (int i = 0; i < maxNum.size(); i++)

                 cout << maxNum[i];

        cout << "\n";

        for (int i = 0; i < minNum.size(); i++)

                 cout << minNum[i];

        cout << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~