https://www.acmicpc.net/problem/2529
2529번: 부등호
두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시
www.acmicpc.net
🔔 문제 :
부등호의 갯수 N과 부등호 문자열이 입력값으로 주어집니다.
그에 맞게 사이사이 숫자를 넣어진 숫자의 최댓값과 최솟값을 찾으면 되는 문제입니다.
예를들면 2 < >가 주어지면
최댓값 : 8 < 9 > 7
최솟값 : 0 < 2 > 1 인 숫자들을 찾으면 됩니다.
🔔 Kick Point :
자리수 별 숫자들을 채워 넣는 것을 DFS를 이용하여 조건에 맞는지 확인하고 숫자를 넣어갑니다.
최댓값과 숫자 9부터 시작하였고 isCheck라는 변수를 이용하여 최솟값을 구했습니다.
예를 들어 부등호 숫자열과 사이사이 숫자가 a < b < c < d > e < f < g > h < i > j 라고 하면
a가 9 일경우 (첫번째 숫자는 조건 예외)
b가 8 일경우 (조건 < 가 거짓이기에 다시 a로)
a가 8 일경우 (첫번째 숫자는 조건 예외)
b가 9 일경우 (조건 < 가 참이기에 c로)
c가 7 일경우 (조건 < 가 거짓이기에 다시 b로)
...
j가 0일경우 ( 조건 > 가 참이고, j까지 찾아기에 조건에 맞는 숫자 구하기 끝)
이런 순서로 진행됩니다.
🔔 Code :
변수
G_n : 부등호 갯수 N값
G_select[MAX] : 자리수 별로 숫자배열
G_MAX[MAX] : 최댓값
G_MIN[MAX] : 최솟값
isCheck : 최대값 최솟값을 넣기위한 변수
G_operators[MAX] : 부등호 문자열
G_visited[MAX] : 숫자별로 사용 됐는지 판단하는 값
함수
Input : G_operators 입력
Check : 부등호 조건에 맞는지 확인
DFS : 자리수에 숫자별로 차례차례 넣어보는 과정
#include <iostream>
using namespace std;
#define endl '\n'
#define MAX 10
int G_n;
int G_select[MAX];
int G_MAX[MAX];
int G_MIN[MAX];
bool isCheck = false;
char G_operators[MAX];
bool G_visited[MAX] = {false, };
void Input(int n) {
for (int i = 0; i < n; i++) {
cin >> G_operators[i];
}
}
bool Check(int idx) {
if (idx < 0) return true;
if (G_operators[idx] == '>') {
if (G_select[idx] > G_select[idx + 1]) return true;
else return false;
}
if (G_operators[idx] == '<') {
if (G_select[idx] < G_select[idx + 1]) return true;
else return false;
}
return false;
}
void DFS(int cnt = 0) {
if (cnt == (G_n + 1)) {
if (!isCheck) {
for (int i = 0; i < (G_n + 1); i++) G_MAX[i] = G_select[i];
}
isCheck = true;
if (isCheck) {
for (int i = 0; i < (G_n + 1); i++) G_MIN[i] = G_select[i];
}
return;
}
for (int i = 9; i >= 0; i--) {
if (!G_visited[i]) {
G_visited[i] = true;
G_select[cnt] = i;
if (Check(cnt-1)) DFS(cnt + 1);
G_visited[i] = false;
}
}
}
int main() {
cin >> G_n;
Input(G_n);
DFS();
for (int i = 0; i < (G_n + 1); i++) {
cout << G_MAX[i];
}
cout << endl;
for (int i = 0; i < (G_n + 1); i++) {
cout << G_MIN[i];
}
}