[브루트 포스 / BOJ 2529 / C++] 부등호

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

2529번: 부등호

1) 0부터 9까지의 순열을 구한다.
2) 구한 순열의 모든 경우의 수를 부등호 사이에 넣어본다.
3) 2)에서 통과한 경우를, long으로 변환한 후 최소값인지 최대값인지 판별한다.
4) 모든 경우의수를 확인하면 최소값과 최대값을 출력한다.

진짜.. 쉬웠는데.. 헛짓거리를 많이했다...

 

문제 풀기전에 우리가  원하는 결과값의 데이터타입을 꼬오오오옥 확인하자

 

아무것도 모르고 atoi(s.c_str) 썼다가 바보짓했다..

 

이 문제는 결과값이 10억이 넘어간다!! long 쓰자!!

 

그냥 Permutation해서 모든 경우의 수를 넣어보면 되는 문제다.!!

 

#include <bits/stdc++.h>

using namespace std;

string res1="0", res2="9999999999", num, t;

char nums[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};


int K;



bool chk(char a, char b, char c){
    
    if(b=='>' && a > c) return true;
        
    
    if(b=='<' && a < c) return true;
    
    return false;
} // 부등호가 맞게 됐다면, true 나머지 경우는 모두 false

void func(string tmp){
    
    string cmpr="";
    
    for(int i = 0 ; i < K ; i++){
        cmpr += tmp[i]; // K번째까지
        cmpr += t[i]; // K번째까지
    }
    cmpr += tmp[tmp.size()-1]; // K+1번째 원소
    
    
    for(int i = 0 ; i < 2*K-1 ; i++){
        if(cmpr[i]=='<' || cmpr[i]=='>') continue;
        if(!chk(cmpr[i], cmpr[i+1], cmpr[i+2])) return; // chk를 했는데 잘못된 연산이라면, 함수 종료.
    }
    
    long int cmpr_int = stol(tmp);
    long int res1_int = stol(res1);
    long int res2_int = stol(res2);
    
    
    if(res1_int < cmpr_int) res1 = tmp; // res1 보다 크면, cmpr이 최대값.
    
    if(res2_int > cmpr_int) res2 = tmp; // res2보다 작으면, cmpr이 최소값.
    
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> K;
    for(int i = 0 ; i < K ; i++){
        char t1;
        cin >> t1;
        t += t1;
    }
    
    
    do{
        string tmp="";
        for(int i = 0 ; i < K+1 ; i++){
            tmp+=nums[i];
        }

        func(tmp);

        
    }while(next_permutation(nums, nums+10));
   
    
    cout << res1 << '\n' << res2;
}

 

태그 : 1780, BOJ, C++, 백준, 재귀, 재귀함수, 종이의 개수