[백준][Python] 2529 부등호

브루트포스, 백트래킹 / 실버 1

﹤﹥

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

2529번: 부등호

 

 

내 풀이

def dfs(n, lst):
    if n == k+1: # 부등호 관계를 만족하는 정수가 만들어진 경우
        ans.append(lst)
        return
    
    for j in range(10):
        if not visited[j]:
            if n == 0:
                visited[j] = True
                dfs(n+1, lst + [j])
                visited[j] = False
            else:
                if eval(str(lst[n-1]) + inequality_sign[n-1] + str(j)):
                    visited[j] = True
                    dfs(n+1, lst + [j])
                    visited[j] = False

k = int(input())
inequality_sign = list(input().split())
visited = [False] * 10
ans = []

dfs(0, []) # 현재 넣은 숫자의 개수, 현재 리스트

print(*ans.pop(), sep='')
print(*ans.pop(0), sep='')

 

 

코드 설명

 

✔️ dfs 함수 내

 

정수의 개수는 무조건 k(부등호 개수) + 1이다.

정수가 모두 만들어진 경우, ans(정답 리스트)에 값을 추가하고 함수를 종료한다.

if n == k+1: # 부등호 관계를 만족하는 정수가 만들어진 경우
    ans.append(lst)
    return

 

정수는 0부터 9까지의 수이며, 중복 선택될 수 없다.

추가하기 전에, 해당 식이 올바른 지부터 검사해야 한다.

추가하려는 정수가 첫 번째 숫자라면 비교할 대상이 없으므로 그냥 추가해 준다.

다른 숫자가 리스트에 있다면, 리스트의 마지막 숫자(비교 대상)와 부등호, 추가할 숫자를 합쳐 식이 성립하는지 검사한다.

식이 성립하는 경우(참인 경우)에만 방문처리한다.

for j in range(10):
    if not visited[j]:
        if n == 0:
            visited[j] = True
            dfs(n+1, lst + [j])
            visited[j] = False
        else:
            if eval(str(lst[n-1]) + inequality_sign[n-1] + str(j)):
                visited[j] = True
                dfs(n+1, lst + [j])
                visited[j] = False

 

 

 

🙀 어려웠던 점

 

시간초과가 발생했다.

 

처음에는 dfs를 무조건 호출하면서 가능한 숫자의 조합을 모두 알아낸 뒤에,

모든 조합의 식을 검사해 ans에 추가할지 말지 결정하였다.

 

이 방식은 dfs()를 너무 자주 호출해야 했다.

함수 호출 전에 검사 과정을 추가해서 식이 성립하지 않는다면 아예 함수를 호출하지 않는 방식으로 변환하였다.