A. 문제설명
https://www.acmicpc.net/problem/2529
2529번: 부등호
여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력�
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. k개의 나열된 부등호가 존재
2. 그 사이에 해당 조건을 만족하는 k+1개의 숫자를 넣고자 한다.
3. k+1의 숫자는 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
4. 여기서, 구해지는 숫자 중 제일 작은 수와 큰 수를 구하라
B. 접근법
DFS
DFS와 가지치기를 이용하면 이 문제를 적은 시간 비용으로 풀 수 있다.
일반적인 줄세우기 문제의 경우 O(N!)의 복잡도지만, 팩토리얼의 특성상 이는 숫자가 조금만 커져도 값이 기하급수적으로 늘어난다. 즉, 필요없는 계산식을 가지쳐 연산을 최대한 줄여야 한다.
일반적인 DFS의 경우 visit[] 배열을 이용해, 모든 조합을 구할 것이다. 그러나 이 문제의 경우 각 부등호의 위치가 고정되어 있으므로 n번째와 n+1번째의 조합을 만들어 다음 깊이로 탐사할 때, 검사하는 조건문을 하나 추가하면 된다.
즉, n번째 부등호 조건에 따라, <인 경우 n번수 < n+1번수인 경우만 재귀호출하도록, >인 경우 n번수 > n+1번수인 경우만 재귀호출하도록 하면 된다.
C. 풀이
1. 0~9의 수까지 k+1의 길이 조합을 만드는 DFS 함수 탐사 시작
2. n번째 부등호 조건에 따라, <인 경우 n번수 < n+1번수인 경우만, >인 경우 n번수 > n+1번수인 경우만 재귀호출
3. 조합을 다 만들었을 시, 최대 최소를 각각 업데이트
D. 내 코드
