[백준 / BOJ / SILVER 2] 2529 번 : 부등호

지나가던 개발자 2020. 3. 17. 23:43

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

2529번: 부등호

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.

www.acmicpc.net

문제 접근 방법

부등호를 기준으로 값을 비교하면서 조건에 맞으면 문자를 더하는 형식으로 진행
문자가 특정 자릿수가 되면 vector에 집어넣어준다
0부터 시작하므로 vector 내부에 최초 값이 최소 값이고 마지막 값이 최대값임을 인지하고 진행

아래는 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
 
using namespace std;
 
int Arr[10];
char Map[10];
bool Select[10];
 
vector<string> Answer;
vector<char> v;
 
bool Check(int Idx, char c)
{
    if (c == '<')
    {
        if (v[Idx] - '0' < v[Idx + 1] - '0')
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else if (c == '>')
    {
        if (v[Idx] - '0' > v[Idx + 1] - '0')
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}
 
bool Calculate(int k)
{
    for (int i = 0; i < k; i++)
    {
        if (Check(i, Map[i]) == false)
        {
            return false;
        }
    }
 
    return true;
}
 
void Dfs(int Cnt ,int k)
{
    if (Cnt == k + 1)
    {
        if (Calculate(k))
        {
            string s = "";
            for (int i = 0; i < v.size(); i++)
            {
                s += v[i];
            }
            Answer.push_back(s);
        }
        return;
    }
 
    for (int i = 0; i < 10; i++)
    {
        if (Select[i] == true)
        {
            continue;
        }
 
        Select[i] = true;
        v.push_back(Arr[i] + '0');
        Dfs(Cnt + 1, k);
        v.pop_back();
        Select[i] = false;
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int k;
    cin >> k;
 
    for (int i = 0; i < k; i++)
    {
        cin >> Map[i];
    }
 
    for (int i = 0; i < 10; i++)
    {
        Arr[i] = i;
    }
 
    Dfs(0, k);
    
    cout << Answer.at(Answer.size() - 1) << "\n";
    cout << Answer.at(0) << "\n";
 
    return 0;
}
Colored by Color Scripter

 