백준 파이썬 2529 부등호

백준 링크:https://www.acmicpc.net/problem/2529

2529번: 부등호

처음부터 끝까지 조건에 맞는 경우를 새는 브루트포스 and 백트레킹 문제인데

부등호를 어떻게 넣나 한참을 생각을 하고 결국 모르겠어서 다른 분들이 푼 해결법으로 해결했다.

n=int(input())
string=list(map(str,input().split()))
nums=[0]*10

min_value=""
max_value=""

def check(i,j,k):
    if k == '<':
        return i < j
    else:
        return j < i


def solve(idx,s):
    global min_value, max_value

    if (idx == n+1):
        if len(min_value) == 0:
            min_value = s
        else:
            max_value = s
        return
    for i in range(10):
        if nums[i] == 0:
            if idx == 0 or check(s[-1],str(i),string[idx-1]):
                nums[i] = 1
                solve(idx+1,s+str(i))
                nums[i] = 0

solve(0,"")
print(max_value)
print(min_value)

min값은 무조건 첫 값이다. 또한 max값은 무조건 맨 끝값이다.

for in 문을 0부터 시작했기때문에

 

부등호 처리를 check 함수를 만들어 FASLE, TRUE 값을 뱉어내개 만들어서 조건식에 맞다면 DFS함수가 이어지게 만들었다.