happy318
팽도리블로그
happy318
전체 방문자
오늘
어제
  • 전체글 (252)
    • 공부 (5)
      • Algorithm 정리 (0)
      • 논문리뷰 (1)
      • C++ (2)
      • Python (2)
      • Java (0)
      • Back-end (0)
      • Front-end (0)
      • Embedded (0)
    • 코딩테스트 (218)
      • Python 문제풀이 (100)
      • C++ 문제풀이 (108)
      • Python template (9)
      • C++ template (1)
    • 일상 (20)
      • 맛집 (13)
      • 쇼핑 (5)
      • 아무 일상 (2)
    • 게임 (9)
      • 메이플스토리 (9)

최근 글

인기 글

hELLO · Designed By 정상우.
happy318

팽도리블로그

코딩테스트/C++ 문제풀이

[백준] 부등호

2023. 3. 26. 17:41

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

 

2529번: 부등호

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력

www.acmicpc.net

우선 문제부터 간단하게 요약하면, 

 

부등호 k개가 주어지면, 해당 부등호 사이 사이에 0~9 사이의 숫자를 넣어 부등호 관계가 성립하도록 하는 최대 정수와 최소 정수를 구해야 하는 문제입니다. 

 

<Soltuion>

최대와 최소를 구해야 하므로, 숫자를 어떻게 뽑아도 무조건 만족하는 것이 있을 것이기 때문에 최대는 9부터 감소시키면서 총 k+1개의 숫자로, 최소는 0부터 증가시키면서 k+1개의 숫자를 사용하여 구하면 되는 것을 알 수 있습니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int k;

/*function which checks order is correct*/
bool check(vector<int> &permut, vector<char> &c){
    for(int i = 0; i < c.size(); i++){
        if(c[i] == '<' && permut[i] > permut[i+1]){
            return false;
        }
        if(c[i] == '>' && permut[i] < permut[i+1]){
            return false;
        }
    }
    return true;
}

int main(){
    // get input
    cin >> k;

    vector<char> c(k); // make vector of size k
    for(int i = 0; i<k; i++){
        cin >> c[i];
    }

    vector<int> small(k+1);
    vector<int> big(k+1);

    // fill vector values
    for(int i = 0; i<k+1; i++){
        big[i] = 9-i;
        small[i] = i;
    }

    // find big
    do{
        if(check(big, c)) break; // if find stop
    }while(prev_permutation(big.begin(), big.end()));
    // find small
    do{
        if(check(small, c)) break; // if find stop
    }while(next_permutation(small.begin(), small.end()));

    // print answer
    for(auto &k: big){
        cout << k;
    }
    cout << '\n';
    for(auto &k: small){
        cout << k;
    }
    cout << endl;

    return 0;
}
반응형

'코딩테스트 > C++ 문제풀이' 카테고리의 다른 글

[백준] 로또  (0) 2023.03.26
[백준] 단어 수학  (0) 2023.03.26
[LeetCode] Zigzag Conversion  (1) 2023.03.21
[LeetCode] Path Sum II  (0) 2023.03.21
[백준] 3의 배수  (0) 2023.03.20
    '코딩테스트/C++ 문제풀이' 카테고리의 다른 글
    • [백준] 로또
    • [백준] 단어 수학
    • [LeetCode] Zigzag Conversion
    • [LeetCode] Path Sum II
    happy318
    happy318

    티스토리툴바