백준 2529 c++ "부등호" -PlusUltraCode-

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

 

[필자 사고]

처음에 어떻게 접근해야 될지 고민했는데

부르트포스 알고리즘이 떠올랐다. 그리고 순서가 있는 조합 느낌이라 백트래킹도 생각이 났다.

그렇다 이 두 알고리즘을 적용하면 해당 문제를 타파할 수 있다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

전역 변수 선언

• int k: 부등호 개수
• char sign[10]: 부등호 기호들을 저장하는 배열 (< 또는 >)
• bool visited[10]: 숫자 0~9 중 현재 사용 중인 숫자를 표시하는 배열
• vector<string> result: 조건을 만족하는 숫자 조합들을 문자열로 저장하는 리스트

---

bool check(char a, char b, char op)

역할: 두 문자 a, b와 부등호 op를 받아서 조건이 참인지 확인하는 함수

• op가 <일 경우 a < b인지 확인
• op가 >일 경우 a > b인지 확인
• 조건을 만족하면 true, 아니면 false를 반환

---

void dfs(int depth, string num)

역할: 깊이 우선 탐색을 통해 가능한 모든 숫자 조합을 생성하는 재귀 함수

• depth: 현재까지 선택한 숫자의 개수
• num: 지금까지 선택된 숫자들을 이어붙인 문자열
• depth == k+1이면 (즉, 숫자가 k+1개 되면) 결과 리스트에 저장
• 숫자 0부터 8까지 중에서 아직 사용되지 않은 숫자(i)를 선택하여:
  • 처음이면 바로 재귀호출
  • 아니면 직전 숫자(num[depth - 1])와 현재 숫자 i가 sign[depth - 1] 부등호를 만족하는지 확인한 후 재귀 호출
  • 호출이 끝난 뒤에는 visited[i]를 다시 false로 복구 (백트래킹)

⚠️ 오류 주의: for (int i = 0; i < 9; i++)는 0~8까지만 탐색하므로 9가 포함되지 않아야 하는 특별한 이유가 없다면 i <= 9로 고쳐야 올바른 탐색이 됩니다.

---

int main()

역할: 프로그램의 시작점

• k와 sign[]을 입력받음
• dfs(0, "")를 호출하여 탐색 시작
• 탐색 후 result 벡터를 사전순으로 정렬
• 정렬된 결과 중 가장 큰 값 (result.back())과 가장 작은 값 (result.front())을 출력

[소스 코드]

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int k;
char sign[10];
bool visited[10];
vector<string> result;

bool check(char a, char b, char op) {
    if (op == '<') return a < b;
    else return a > b;
}

void dfs(int depth, string num) {
    if (depth == k + 1) {
        result.push_back(num);
        return;
    }

    for (int i = 0; i < 9; i++) {
        if (!visited[i]) {
            if (depth == 0 || check(num[depth - 1], i + '0', sign[depth - 1])) {
                visited[i] = true;
                dfs(depth + 1, num + to_string(i));
                visited[i] = false;
            }
        }
   }
}

int main() {
    cin >> k;
    for (int i = 0; i < k; i++) cin >> sign[i];

    dfs(0, "");

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

    cout << result.back() << '\n';
    cout << result.front() << '\n';

    return 0;
}