[백준 2592] 부등호

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

2529번: 부등호

 

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

 

 

아이디어

일단 처음에는 백트랙킹으로 모든케이스에 대하여 조사해서 풀었다. 결과적으로는 풀린다.

 

그러나 그렇게하면 멍청한 아이디어였다. 간단히 생각하자. 5자리수가 필요하다 하면

 

최솟값은 01234 에서 조사하면 되고

최대값은 98765 에서 조사하면 된다

 

어차피 부등호 방향은 만족하는 경우의수를 무조건 구할 수 있다

 

아래는 걍 무식하게 구한거..

N = int(input())
import sys
arr = sys.stdin.readline().rstrip().split(' ')

minVal = 9999999999
maxVal = -1
maxStr = ''
minStr = ''
def stringfy(arr):
    s = ''
    for i in arr:
        s+=str(i)
    return s
def dfs(arr, save, visit):
    saveSize = len(save)
    if saveSize > len(arr):
        global minVal
        global maxVal
        global minStr
        global maxStr
        s  = stringfy(save)
        snum = int(s)
        if minVal > snum:
            minVal = snum
            minStr = s
        if maxVal < snum:
            maxVal = snum
            maxStr = s
        return
    for i in range(10):
        if visit[i]:
            continue
        if saveSize:
            if arr[saveSize -1] == '>' and save[-1] > i:
                visit[i] = True
                save.append(i)
                dfs(arr,save,visit)
                save.pop()
                visit[i]=False
            elif arr[saveSize -1] == '<' and save[-1] < i:
                visit[i] = True
                save.append(i)
                dfs(arr,save,visit)
                save.pop()
                visit[i]=False
        else:
            visit[i] = True
            save.append(i)
            dfs(arr,save,visit)
            save.pop()
            visit[i]=False

visit = [False] * 10
save = []
dfs(arr,save,visit)

print(maxStr)
print(minStr)