이번에는 백준 2529번 부등호 문제를 풀어보았습니다.
문제를 처음 봤을 때 0부터 9까지의 숫자를 중복 없이 선택해야 하고, 모든 부등호 조건을 만족해야 했기 때문에 DFS를 이용한 완전 탐색으로 해결할 수 있다고 생각했습니다.
숫자를 하나씩 선택하면서 현재까지의 부등호를 만족하는 경우만 계속 탐색하도록 구현하였습니다.
모든 숫자를 선택한 경우에는 현재 수와 기존의 최댓값, 최솟값을 비교하여 갱신하였습니다.
문제 설명
0부터 9까지의 서로 다른 숫자를 이용하여 부등호를 만족하는 수를 만들어야 합니다.
각 숫자는 한 번만 사용할 수 있으며, 모든 부등호를 만족해야 합니다.
만들 수 있는 수 중 최댓값과 최솟값을 출력하는 문제입니다.
풀이 아이디어
DFS를 이용하여 숫자를 하나씩 선택하였습니다.
이미 선택한 숫자는 다시 사용할 수 없도록 관리하였습니다.
현재 숫자를 선택할 때는 이전 숫자와 현재 숫자가 부등호를 만족하는 경우에만 DFS를 계속 수행하였습니다.
숫자를 모두 선택한 경우에는 현재 만들어진 수와 기존의 최댓값, 최솟값을 비교하여 갱신하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int num_arr[10] = {0,1,2,3,4,5,6,7,8,9}, used[10];
int k;
vector<char> sign;
vector<int> ret;
vector<int> max_ret;
vector<int> min_ret;
bool calculate(int level, int first, int second) {
if (sign[level] == '<')
return first < second;
else
return first > second;
}
void dfs(int level) {
if (level == k+1) {
for (int i=0; i<=k; i++) {
if (ret[i] == max_ret[i])
continue;
else {
if (ret[i] > max_ret[i]) {
max_ret = ret;
}
break;
}
}
for (int i=0; i<=k; i++) {
if (ret[i] == min_ret[i])
continue;
else {
if (ret[i] < min_ret[i]) {
min_ret = ret;
}
break;
}
}
return;
}
for (int i=0; i<10; i++) {
if (used[i] == 1) continue;
if (level != 0 && !calculate(level-1, ret[level-1], i)) continue;
ret.push_back(i);
used[i] = 1;
dfs(level+1);
used[i] = 0;
ret.pop_back();
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> k;
max_ret.resize(k+1);
min_ret.resize(k+1);
fill(max_ret.begin(), max_ret.end(), 0);
fill(min_ret.begin(), min_ret.end(), 9);
for (int i=0; i<k; i++) {
char s;
cin >> s;
sign.push_back(s);
}
dfs(0);
for (int i=0; i<=k; i++) {
cout << max_ret[i];
}
cout << '\n';
for (int i=0; i<=k; i++) {
cout << min_ret[i];
}
cout << '\n';
return 0;
}풀이 흐름
- 부등호를 입력받아 저장합니다.
- DFS를 이용하여 숫자를 하나씩 선택합니다.
- 이미 사용한 숫자는 선택하지 않습니다.
- 현재 부등호를 만족하는 경우에만 다음 단계로 이동합니다.
- 숫자를 모두 선택한 경우 최댓값과 최솟값을 비교하여 갱신합니다.
- 모든 경우를 탐색한 뒤 결과를 출력합니다.
구현 포인트
1. 사용한 숫자 관리
같은 숫자를 두 번 사용할 수 없기 때문에 used 배열을 이용하여 관리하였습니다.
if (used[i] == 1) continue;숫자를 선택하면 사용 표시를 하고, DFS가 끝나면 다시 해제하였습니다.
used[i] = 1;
dfs(level+1);
used[i] = 0;2. 부등호 검사
현재 숫자를 선택하기 전에 이전 숫자와 부등호를 만족하는지 확인하였습니다.
if (level != 0 && !calculate(level-1, ret[level-1], i))
continue;부등호를 만족하는 경우에만 다음 단계로 탐색을 진행하였습니다.
3. 부등호 계산 함수
부등호 비교는 별도의 함수에서 수행하였습니다.
bool calculate(int level, int first, int second)현재 부등호가 <인지 >인지에 따라 결과를 반환하도록 구현하였습니다.
if (sign[level] == '<')
return first < second;
else
return first > second;4. 최댓값 갱신
숫자를 모두 선택한 경우 현재 수와 기존 최댓값을 앞자리부터 비교하였습니다.
if (ret[i] > max_ret[i]) {
max_ret = ret;
}처음으로 다른 자리가 나오는 순간 비교를 종료하도록 구현하였습니다.
5. 최솟값 갱신
최솟값 역시 같은 방식으로 앞자리부터 비교하여 갱신하였습니다.
if (ret[i] < min_ret[i]) {
min_ret = ret;
}모든 경우를 탐색한 뒤 최댓값과 최솟값을 출력하였습니다.
