1038 감소하는 수

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

#부분 집합

#백 트래킹

1038번: 감소하는 수

#답지

import sys

sys.setrecursionlimit(10 ** 9)

def solve(n):

cnt = 0
#cnt가 n이 되면 종료
num = 1
#말그대로 넘버 n번째 감소하는 수
while True:

str_num = str(num)
#num을 str화
flag = True
#flag True
if len(str_num) == 1: # 길이가 1이면 무조건 감소하는 수

pass
#num이 일의 자리 수면 패스

else:

for i in range(1, len(str_num)):
#최대자리수 빼고 돌림

if int(str_num[i]) < int(str_num[i - 1]):
#만약 감소하는 수면 continue

continue

else:
# 7654432 면 i는 4이다.
#7655032 이런식인듯

#i가 감소하는 수가 아니라면

start = str_num[:i - 1]
#start= i값에서 -2 뺀거까지의 값

mid = str(int(str_num[i - 1]) + 1)
#mid=i값에서 -1뺀거의 값에서 1 더함

end = '0' + str_num[i + 1:]
#'0' 더하기 i+1부터의 값

num = int(start + mid + end)
# 다 합침

flag = False

# 찾지 못하면 False

 

break

 

if flag:

cnt += 1

if cnt == n: # n번째 감소하는 수

 

return num

num += 1

#찾으면 cnt세주고 값을 1올림으로써 다음 감소하는 수 찾기

 

 

 

if __name__ == "__main__":

n = int(sys.stdin.readline())

if n >= 1023: # 1022: 9876543210

print(-1) # N번째 감소하는 수 x

elif n == 0:

print(0)

else:

print(solve(n))

 

#아이디어

 

부분집합으로 취급해서 9876543210 을 넣냐 안 넣냐로 코드를 짜는 것이다.

 

그럼 2^10 총 1024 가지 인데 여기서 0번째 와 아무것도 사용하지 않는 경우의 수 제외

 

n번째 수만 찾으면 되는것이다. 백트래킹을 이용해서 구해준다. 흥미로운건 n번쨰 수인지 판별할때

 

flag를 사용했다는 것과 str과 int를 넘나들면서 구헀다는 것이다.