유형 : dp라고 쓰여있지만 완전탐색...
문제풀이
10,21,321 처럼 큰 자리의 숫자가 작은 자리의 숫자보다 큰 숫자를 구하는 문제로, 결국 [0,1,2,3,4,5,6,7,8,9] 만들 수 있는 모든 subset을 구하는 문제와 동일하다.
무슨 말인가 하니, 위의 0 ~ 9 숫자 중 중복되지 않는 n개의 숫자를 뽑으면 그 숫자들로 만들 수 있는 감소하는 숫자는 1개밖에 존재하지 않는다. 예를 들어 1,3,5를 골랐다면 531 이외의 가능한 감소하는 수는 없다. 따라서 1 ~ 9로 만들수 있는 감소하는 수의 총개수는 $2^{10} -1$ 개가 되는데, 그 이유는 0 ~ 9 총 10개의 숫자 모두 선택한다, 안 한다 두 개의 경우가 존재하기 때문이다. 따라서 입력값 n이 1024 이상인 경우에는 -1을 반환하면 된다(실제 구현할 때는 0부터 셈으로 1023 이상). 1023 이하인 경우에는, 10개의 숫자 중 뽑는 n개의 숫자를 1개부터 10개까지 늘리며 모든 가능한 조합으로 숫자를 만든 후, 정렬하여 n번째 수를 반환하면 된다.
Python Code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
import sys
sys.setrecursionlimit(1000000)
global num
num = [9,8,7,6,5,4,3,2,1,0]
digit = 2
temp = [0 for i in range(2)]
global ans
ans =[]
i=0
def dfs(arr,digit,depth):
global num
global ans
if depth == digit:
t=0
while digit>0:
t+=arr[len(arr)-digit]*10**(digit-1)
digit-=1
ans.append(t)
return
for i in range(num.index(arr[depth-1])+1,10-(digit-depth)+1):
arr[depth]=num[i]
dfs(arr.copy(),digit,depth+1)
n = int(input())
if n >= 1023:
print(-1)
else:
for digit in range(1,11):
arr = [0 for i in range(digit)]
for i in range(10-digit+1):
arr[0]=num[i]
dfs(arr,digit,1)
if len(ans) >= n+1:
break
ans.sort()
print(ans[n])
|
cs |
21 line 은, depth번째 수 i 로 가능한 것들의 조건인데, i는 depth-1보다는 작아야 하고, 앞으로 digit-depth 만큼의 수를 더 뽑아야 하기 때문에, 뒤에 digit-depth만큼의 수는 남겨두어야 한다.
29 line의 digit이 위에서 말한 n(몇 개를 선택할 것인지로 몇 자릿수의 숫자를 만들지를 의미)이다.
문제 링크
1038번: 감소하는 수
음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.
www.acmicpc.net
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 17478 재귀함수가 뭔가요? (0) | 2020.03.08 |
|---|---|
| 백준 2293 동전 1 (0) | 2020.03.01 |
| 백준 2157 여행 (0) | 2020.02.27 |
| 백준 2579 계단 오르기 (0) | 2020.02.27 |
| 백준 4949 균형잡힌 세상 (0) | 2020.02.25 |