(Python) - BOJ(1038번) : 감소하는 수

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

1038번: 감소하는 수

 

• 해설 :

음이 아닌 정수 X가 가장 큰 자릿수부터 가장 작은 자릿수까지 감소한다면 (숫자가 작아진다면) 이는 감소하는 수 이다.

N이 주어질 때 0부터 시작하는 감소하는 수들 중 N번째 수를 출력하는 문제이다 (숫자는 1,000,000) 이하이다.

 

 

 

 

• 풀이 :

완전 탐색 문제이다.

N번째 수인지 확인하는 cnt 변수를 두고, 이 cnt 변수가 N보다 작은동안 1부터 1,000,000까지 모든 수들에 대해 감소하는 수인지 확인한다. 이 때, 1022번째부터는 값의 범위가 1,000,000을 넘어가므로 이전값까지 확인하면 된다.

감소하는 수인지 확인할 땐, 각 자릿수별로 잘라서 이전 값과 비교하는 방법을 사용했다.

 

 

 

 

import sys
input = sys.stdin.readline
 
def findpath(N):
    num = 1
    cnt = 0
    if N >= 1023:
        return -1
    if N == 0:
        return cnt
    while True:
        length = str(num)
        f = True
        if len(length) == 1:
            pass
        else:
 
            for i in range(1,len(length)):
                if int(length[i]) < int(length[i-1]): # 감소하는 수 인지
                    continue
                else:
                    start = length[:i - 1]
                    mid = str(int(length[i - 1]) + 1)
                    end = '0' + length[i + 1:]
                    num = int(start + mid + end)
                    f = False
                    break
        if f:
            cnt +=1
            if cnt == N:
                return num
            num += 1
 
if __name__ == "__main__":
    N = int(input())
    print(findpath(N))