Gidhub BE Developer

[BOJ] 2529. 부등호

2018-09-24
goodGid

Problem

Problem URL : 부등호


[1] Answer Code (18. 09. 24)

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

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); cout.tie(0);
    
    int n;
    cin >> n;
    for (int i = 0; i<n; i++){
        char temp;
        cin >> temp;
        sign += temp;
    }
    //최대
    for (int i = 9; i > 9 - (n + 1); i--)
        maxNum.push_back(i);
    while (1){
        if (valid(maxNum))
            break;
        prev_permutation(maxNum.begin(), maxNum.end());
    }
    
    //최소
    for (int i = 0; i < (n + 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 << endl;
    
    for (int i = 0; i < minNum.size(); i++)
        cout << minNum[i];
    cout << endl;
    
    return 0;
}

Review

  • 부등호가 2개라면 3개의 숫자로 조건을 완성시킬 수 있다.

  • 그래서 문제의 조건을 보면 K의 범위는 최대 9개이다.

  • 그래야만 0~9 총 10개로 표현이 가능하기 때문이다.

  • next_permutationprev_permutation의 동작 예시를 순열(Permutation) 글 에 정리해놨다.

  • 백준 2529번 부등호 블로그를 참고해서 풀이했다.


Comments

Content