[BOJ] 1038. 감소하는 수

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

1038번: 감소하는 수

 

 

1. 해결방법

이 문제는 완전 탐색 백트래킹으로 해결한 문제이다.
( + 조합으로도 해결 )

처음엔 ''문자열을 시작으로 0부터 9까지의 값을 문자열에 더하면서 answer 리스트에 append 하였다.
재귀를 통해서 계속해서 문자열을 추가시켜 sort() 정렬을 해주면 감소하는 수의 리스트가 만들어진다.

 

 

2. 정답코드

(1) 백트래킹

import sys
input = sys.stdin.readline

N = int(input())
answer = []


def dfs(number):
    if len(number) == 0:
        for i in range(10):
            answer.append(int(i))
            dfs(number + str(i))

    else:
        for i in range(10):
            if int(number[-1]) > i:
                answer.append(int(number + str(i)))
                dfs(number + str(i))


dfs('')
answer.sort()

print(answer[N] if len(answer) > N else -1)

 

(2) 조합

import sys
from itertools import combinations
input = sys.stdin.readline

N = int(input())
answer = []


# 순열
for i in range(1, 11):
    for j in combinations(range(10), i):
        numbers = sorted(list(j), reverse=True)
        answer.append(int(''.join(map(str, numbers))))

answer.sort()
print(answer[N] if len(answer) > N else -1)