백준 - 감소하는 수(1038)

marafo·2020년 12월 31일
0

Brute Force + Back Tracking

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.


시간초과 code

import sys

N = int(sys.stdin.readline())
count = 10
num = 11

if(N < 10):
    print(N)

while True:
    target = list(str(num))
    for i in range(len(target) - 1):
        a = 0
        if int(target[i]) > int(target[i + 1]):
            a += 1
        else:
            break
            
    if a == len(target) - 1:
        count += 1
    
    if count == N:
        print(num)
        break
    else:
        num += 1

정답(솔루션 검색)

import sys

n = int(sys.stdin.readline())
count = -1
answer = -1

def solution(limit, sub):
    global count
    global answer
    if len(sub) == limit:
        count += 1
        
        if count == n:
            answer = int(sub)
            print(answer)
            sys.exit()
        return
    else:
        if sub == '':
            for i in range(limit - 1, 10):
                sub += str(i)
                solution(limit, sub)
                sub = ''
        else:
            for i in range(int(sub[-1])):
                if limit - len(sub) - 1 > i:
                    continue
                sub += str[i]
                solution(limit, sub)
                sub = sub[:-1]
                
for k in range(1, 11):
    solution(k, '')
print(-1)
    
#---------------------------------------------------------

def get_dec(num, dec_nums, digit = 1): # digit => 자릿수
    
    if digit > 10:
        return 
    
    dec_nums.append(num)
    
    for i in range(10):
        if (num % 10) > i :
            get_dec((num * 10) + i, dec_nums, digit = digit + 1)
            
    return dec_nums

n = int(input())
dec_nums = []

for num in range(10):
    r = get_dec(num, dec_nums)
    
r.sort()

if n >= 1023:
    print(-1)
else : 
    print(r[n])

참고)
https://hose0728.tistory.com/86
https://roseline124.github.io/algorithm/2019/04/16/Algorithm-baekjoon-1038.html

profile
프론트 개발자 준비

0개의 댓글