[백준/파이썬(Python)] 부등호 2529

💌문제

---

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

2529번: 부등호

 

 

💌풀이

---

백트래킹으로 풀어야 하는 문제!!

백트래킹,, 너무 어렵다

 

일단 숫자와 부등호를 입력받아서 부등호가 <이거나 >일때 두 숫자의 비교관계가 맞는지 틀린지 반환해주는 함수를 만든다.

백트래킹의 탈출 조건은 깊이가 n+1일때. 부등호 갯수가 n이니 숫자는 n+1이 있어야 하기 때문이다.

이때, 최솟값자리가 비어있으면 거기에 지금까지 구한 s를 넣고, 아니라면 최댓값자리에 넣는다.

왜냐면… 가장 먼저 조건에 전부 맞는 숫자가 최솟값이기 때문이다. 백트래킹을 할 때는 사전순으로 구하게 되니까.

그래서 최솟값 자리가 비어있다면 먼저 넣어주고,

그게 아니라면… 최댓값 자리에 넣어줌으로써, 최종적으로 백트래킹 함수가 끝나면 가장 최댓값이 저장될 것이다.

그리고 루프를 1~9까지 돌면서 만약 아직 방문하지 않았다면,

깊이가 0이고(아직 아무런 숫자도 넣지 않았고) check함수를 통해 확인했을 때 부등호 관계가 맞다면 방문처리를 해주고 깊이와 문자열에 현재 숫자를 넣고 재귀를 돌린다.

돌다가 모순이 발생하면 되돌아 오기 때문에 방문처리를 다시 False로 돌린다.

 

💌파이썬 코드

---

n=int(input())
st=list(map(str,input().split()))
visited=[0]*10
max_ans=''
min_ans=''

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

def solve(idx,s):
    global max_ans,min_ans
    if (idx==n+1):
        if(len(min_ans)==0):
            min_ans=s
        else:
            max_ans=s
        return
    for i in range(10):
        if (visited[i]==0):
            if (idx==0 or check(s[-1],str(i),st[idx-1])):
                visited[i]=True
                solve(idx+1,s+str(i))
                visited[i]=False

solve(0,'')
print(max_ans)
print(min_ans)