문제

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

백트래킹 연습

해결방법1 - 조합

평소에 내가 자주 사용하는 조합방식이다.

from itertools import combinations

n = int(input())
result = set()

for i in range(1,11):
    for com in combinations(range(0,10),i):
        com = sorted(com,reverse=True)
        result.add(int(''.join(map(str,com))))
result = sorted(result)

try:
    print(result[n-1])
except IndexError:
    print(-1)

주어진 조건 안에 있는 모든 수의 조합을 구하여 배열을 만든 후 출력

해결방법2 - 백트래킹

N-Queen 이후로 느끼는 거지만 백트래킹이 정말 약하다.
지속적으로 백트래킹을 풀려고하고 유망한지, 넣었다 다시 삭제해줬는 여부를 능숙하게 사용해야할 것 같다.

n = int(input())
result = set()
number = []

def dfs():
    # 추가해주고
    if number:
        result.add(int(''.join(map(str,number))))
    
    for i in range(10):
        # 무조건 추가해주거나 오른쪽이 작은 경우라면
        if not number or number[-1] > i:
            number.append(i)
            dfs()
            number.pop()

dfs()

result = sorted(result)
print(result[n-1] if len(result) >= n else -1)

하나씩 추가해주며 수로 만들어 집합에 넣어 유효한 숫자를 만들었다. 그리고 조건에 맞는 출력을 했다.