https://www.acmicpc.net/problem/2529
2529번: 부등호
여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력
www.acmicpc.net
백트래킹을 이용한 풀이는
코드가 직관적이므로 별도로 설명하진 않겠습니다.
백트래킹 코드
#include <bits/stdc++.h>
using namespace std;
int n;
char arr[20];
bool ch[10];
int path[20];
long long minn = LLONG_MAX, maxx = LLONG_MIN;
void DFS(int L) {
if (L == n + 1) {
for (int i = 1; i <= n; i++) {
if (arr[i] == '<') {
if (path[i - 1] > path[i]) {
return;
}
}
else {
if (path[i - 1] < path[i]) {
return;
}
}
}
long long x = 0;
for (int i = 0; i < L; i++) {
x = x * 10 + path[i];
}
minn = min(minn, x);
maxx = max(maxx, x);
}
else {
for (int i = 0; i <= 9; i++) {
if (ch[i] == 0) {
ch[i] = 1;
path[L] = i;
DFS(L + 1);
ch[i] = 0;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
long long comp = pow(10, n);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
DFS(0);
cout << maxx << '\n';
if (minn < comp) {
cout << 0;
}
cout << minn << '\n';
return 0;
}
백준 2529 부등호 위상정렬로 푸는 법
위상정렬을 공부하다 다른 블로그의 설명을 많이 봤는데 이해가 잘 되지 않았어서
한참 헤맸습니다.
노드 번호와 해당 노드의 숫자를 별개로 생각해야합니다.
A노드와 B 노드가 있다고 가정합니다.
부등호를 기준으로
A > B 라면 A -> B 를 향하는 간선을 주고
위상정렬을 수행합니다.
예제에서 먼저 최댓값을 생각해보면
2
< >A < B > C 이면
B -> A
B -> C 가 간선이 되고
위상정렬을 수행하면 순서가
B A C 이거나
B C A 가 됩니다.
이 뜻은 B가 가장 커야하고 A와 C는 따로 정해주어야 한다는 뜻입니다.
그래서 B는 9가 되고 A C 가 8 7이 되어야 하는데
최댓값을 구할 때 먼저 나온게 커야하므로 A에 8을 주고 C에 7을주면
B : 9 ,
A : 8,
C : 7,
이 되고 원래 숫자는 ABC 순서이므로
897이 최대가 됩니다.
최솟값을 구할 땐
가장 큰 수인 B에 숫자를 넣을 때 9부터 넣는게 아닌 K(2)부터 넣어야 최솟값이 구해집니다.
그리고 A 와 C를 정할 때 앞에 있는 숫자가 작은 숫자여야 최솟값이 되므로 A에 0 C에 1을 넣으면 됩니다.
그러면
B : 2
A : 0
C : 1
이므로 정답은 ABC 021이 됩니다.
간선 정보는 동일하게 이용하고 degree(차수)를 줄여주면서 큐를 돌 때
노드번호를 각각 최소힙, 최대힙으로 주면서 뽑아주면서
노드에 숫자를 하나씩 넣으면 됩니다.
위상정렬 코드
#include <bits/stdc++.h>
using namespace std;
int k;
char arr[20];
int node[11]; // 최댓값 구하는데 사용
int degree[11];
int node2[11]; // 최솟값 구하는데 사용
int degree2[11];
bool ch[11][11];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k;
for (int i = 1; i <= k; i++) {
cin >> arr[i];
if (arr[i] == '<') {
ch[i + 1][i] = 1;
degree[i]++;
degree2[i]++;
}
else{
ch[i][i + 1] = 1;
degree[i + 1]++;
degree2[i + 1]++;
}
}
priority_queue<int> Q;
//최댓값 구하기
for (int i = 1; i <= k + 1; i++) {
if (degree[i] == 0) {
Q.push(-i);
}
}
int cnt = 9;
while (!Q.empty()) {
int x = -Q.top();
Q.pop();
node[x] = cnt--;
for (int i = 1; i <= k + 1; i++) {
if (ch[x][i] == 1) {
if (--degree[i] == 0) {
Q.push(-i);
}
}
}
}
for (int i = 1; i <= k + 1; i++) {
cout << node[i];
}
cout << '\n';
//최솟값 구하기
for (int i = 1; i <= k + 1; i++) {
if (degree2[i] == 0) {
Q.push(i);
}
}
cnt = k;
while (!Q.empty()) {
int x = Q.top();
Q.pop();
node2[x] = cnt--;
for (int i = 1; i <= k + 1; i++) {
if (ch[x][i] == 1) {
if (--degree2[i] == 0) {
Q.push(i);
}
}
}
}
for (int i = 1; i <= k + 1; i++) {
cout << node2[i];
}
cout << '\n';
return 0;
}
위상정렬을 이용했을 때 시간은 0ms
백트래킹을 이용했을 때 120ms
백트래킹에서 가지치기를 하진 않았지만, 위상정렬을 이용할 때
더 빠른 시간 내에 문제를 해결 할 수 있습니다.
'Algorithm > problem' 카테고리의 다른 글
| 백준 2056번: 작업 - 위상정렬 dp C++ 코드 (0) | 2022.02.25 |
|---|---|
| 백준 21276번 : 계보 복원가 호석 - 위상정렬 C++ 코드 (0) | 2022.02.25 |
| 백준 14442번 : 벽 부수고 이동하기 2 - BFS C++ (0) | 2022.02.24 |
| 백준 3665번 : 최종 순위 - 위상정렬 C++ 문제풀이 및 코드 (0) | 2022.02.24 |
| 백준 2637번 : 장난감 조립 - 위상정렬 dp C++ (0) | 2022.02.24 |
