[백준] 2529 - 부등호 (C++)

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

두 종류의 부등호 기호 '<'와 '>'가 k개 나열된 순서열 A가 존재하고, 부등호 기호 앞 뒤에 서로 다른 한 자릿수 숫자(0~9)를 넣어 모든 부등호 관계를 만족시키는 (k+1)자리의 정수 중 최댓값과 최솟값을 찾는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 2 ≤ k ≤ 9
• 첫 자리가 0인 경우도 정수에 포함하고, 출력 정수는 하나의 문자열이 돼야 함

 

백트래킹으로 모든 (k+1)자리의 수를 구하고 조건이 맞는다면 집합에 넣어 그 중 최댓값과 최솟값을 찾으면 될 것 같다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. k와 k개의 부등호 입력 받기
2. dfs 함수로 (k+1)자릿수의 정수를 찾고, 조건이 맞으면 집합에 삽입 (첫 자리가 0이어도 포함)
   1. 조건: 모든 부등호 관계를 만족시킴
3. 집합에 있는 정수 중 최댓값과 최솟값 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

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

int k,nums[10];
bool visit[10];
char ne[10];
set<string> s;

void dfs(int d, string chr) {
    if (d==k+1) {
        for (int i=0; i<k; i++) {
            if (ne[i]=='<' && nums[i] > nums[i+1] || ne[i]=='>' && nums[i] < nums[i+1]) {
                return;
            }
        }
        s.insert(chr);
        return;
    }
    for (int i=0; i<10; i++) {
        if (!visit[i]){
            visit[i] = true;
            nums[d] = i;
            dfs(d+1, chr+to_string(i));
            visit[i] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> k;
    for (int i=0; i<k; i++) cin >> ne[i];

    dfs(0,"");

    cout << *max_element(s.begin(), s.end()) << '\n' << *min_element(s.begin(),s.end());
}