2529 : 부등호 - 백트래킹, 순열

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

2529번: 부등호

문제요약

상하좌우로 피는 꽃 세 송이를 최소 비용으로 심기

 

난이도

Silver 2

---

풀이 포인트

• 백트래킹
  • 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
• 순열
  • do while(next permutation) : 순열 돌리며 확인할 수 있는 방법
• 문자열 대소 비교
  • '23'과 '123'의 경우 : 앞쪽 한 자리수부터 대소비교를 시작하기 때문에 23이 더 큰 숫자로 판정됨 주의

---

REVIEW

 

우선 풀고 보자라는 생각에 너무 단순하게 구현한 듯하다.

순열을 완탐하겠다는 건 굉장히 시간복잡도(10!)가 높은 방법인데 어찌저찌 풀었지만

모범답안을 이해해 봐야겠다.

 

그리고 계속해서 예제 입력을 했더니 생각과 다른 길이의 문자열이 출력이되어서 곤란했는데

문자열의 size를 고정하고 비교하니 어찌저찌 대소비교가 가능했다.

 

하지만, 문자열일 경우 23과 123의 대소 비교시 23이 더 큰 숫자로 나온다는 사실을

간과하지 않았어야 명확하게 코드를 돌릴 수 있었을 것!

 

그리고 반복문을 여러겹으로 짤 때 return, break, continue의 시점과 실행순서가 헷갈릴 때가 많다.

이것도 계속 디버깅해보면서 공부하기!

---

CODE

#include <bits/stdc++.h>
using namespace std;

vector<int> a = {0,1,2,3,4,5,6,7,8,9};
int n;
char c;
vector<char> p;
string ret;
vector<string> b;

int main(){

    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> c;
        p.push_back(c);
    }

    do{     

        // cout << "현재 순열은 " ;
        // for(int i : a) {cout << i;}
        // cout << endl;

        ret = "";

        if(p[0] == '<'){
            if(a[0] > a[1]) continue;
            //cout << "첫번째 요소 합격\n";
            ret += to_string(a[0]);
            ret += to_string(a[1]);
        }

        if(p[0] == '>')
        {
            if(a[0] < a[1]) continue;
            //cout << "첫번째 요소 합격\n";
            ret += to_string(a[0]);
            ret += to_string(a[1]);
        }

        for(int i = 1; i < n; i++){

            if(p[i] == '<'){
                
                if(a[i] > a[i+1]) break;           
                ret+= to_string(a[i+1]);
            }else if(p[i] == '>') {
                if(a[i] < a[i+1]) break;             
                ret+= to_string(a[i+1]);
            }
        }

        //cout << "현재 ret에 담긴 것은 " << ret <<'\n';

        if(ret.size() == n+1){
            b.push_back(ret);
        }
        
       

    }while(next_permutation(a.begin(),a.end()));


    sort(b.begin(), b.end());

    cout << b[b.size()-1]<<'\n';
    cout << b[0];
}

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

// 10! = 362만, 1억보단 작다.
// 즉 완탐해도 되는구나 하고 들어가기!

int n, check[10];
char a[20];
vector<string> ret;  


bool good(char x, char y, char op){ 
	if(x < y && op == '<') return true; 
	if(x > y && op == '>') return true; 
	return false; 
}

void go(int idx, string num){ 
	if(idx == n + 1){
		
		ret.push_back(num); return;
	}

	for(int i = 0; i <= 9; i++){
		if(check[i]) continue; 
        
        // 문자로 더해주는 식
		if(idx == 0 || good(num[idx - 1], i + '0', a[idx - 1])){
			check[i] = 1;
			go(idx + 1, num + to_string(i));
			check[i] = 0;
		}
	}

	return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL); 

    cin >> n; 
    for(int i = 0; i < n; i++) cin >> a[i]; 

    go(0, "");

    sort(ret.begin(), ret.end());
    cout << ret[ret.size() - 1] << "\n" << ret[0] << "\n";
}

// 문자열 대소비교 size먼저 체크하는 것이 중요!
// 23, 123 비교하면 23이 더 크게 판단되기 때문!

// 문자 vs 숫자 : 아스키코드 순으로 비교하게 되기 때문