-
1038. [Python]감소하는 수Python_알고리즘/Gold V 2023. 9. 8. 16:42
1. 문제
https://www.acmicpc.net/problem/1038
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- 백트래킹
- 브루트포스
3. 파이썬 코드
# 문자열 체크하는 함수 def checking(num, M): # 글로벌 문자 변수 선언 global check global cnt global ans # M 의 길이가 1로 끝일때 if M == 1: # 이전의 check 값과 num[0] 값의 크기를 비교해 작으면 cnt += 1 if check > int(num[0]): cnt += 1 # 외의 경우 ans = 1 반환 else: ans = 1 return # check 값이 비어있는 경우 if check == "": # num[0]의 값을 초기값으로 넣어줌 check = int(num[0]) # 1 ~ 끝 까지 M은 문자열 길이로 생각해서 -1 해서 넣어줌 checking(num[1:], M-1) # check에 값이 있는 경우 else: # check 보다 값이 작은 경우 재귀 if int(num[0]) < check: check = int(num[0]) checking(num[1:], M-1) # 외의 경우 else: # ans 에 현재 문자열의 길이 M 넣어줌 ans = M return N = int(input()) # N 이 10보다 작은 경우 N 출력 if N < 10: print(N) # 외의 경우 else: # cnt 초기값 9, number는 10 으로 선언 cnt = 9 number = 10 # 2자리수부터 비교하기 때문에 num_length 2로 선언 num_length = 2 # cnt 값이 1,000,000 이하까지 while cnt <= 10**6: # check 값 ""로 초기화 check = "" # ans에 문자열 길이 넣어줌 ans = len(str(number)) # ans 값이 num_length 보다 크면 ans 값으로 갱신 if ans > num_length: num_length = ans # 함수 실행 => number 문자열, 문자열 길이 인자로 넣어줌 checking(str(number), ans) # 초기값과 같은 경우 if ans == num_length: # cnt 값이 증가했기 때문에 number + 1 number += 1 # 초기값과 다른 경우 else: # number 값의 몫의 +1 해서 10**ans 한 값을 넣어줌 number = (number//(10**ans) + 1) * (10**ans) # cnt 값이 N과 같은 경우 if cnt == N: # number 에서 -1 한 값 출력 후 반복문 탈출 print(number-1) break # 만약 9 넘어갈 경우 -1 출력 if num_length > 10: print(-1) break
4. 문제를 풀고난 후 생각
- N의 값은 몇번째 수인지 찾는 문제였고 최대 1,000,000 번째 수까지 물어보는 문제였다.
- number 로 값을 1씩 증가시키며 10미만이였을 경우 0~9 값을 그대로 출력해줬고, 10부터 넘어갈 때마다 함수를 사용해서 cnt 값을 증가시켰다.
- 10이 올경우 check = 1 을 넣고 재귀를 통해 0 을넣어 1과 0을 비교해서 작으면 cnt 증가 외의 경우 ans = 1을 반환해줬고 ans 값을 통해서 몇번째 자리에서 반환됐는지 체크를 해줬다.
- 이 체크한 값을 바탕으로 3221 이 들어갈 경우 322 까지 값을 확인한 후 2번째 자리에서 이후 어느 값이오든 작기 때문에 3221에서 불필요한 연산없이 3300으로 넘어갈 수 있도록 ans 값을 활용했다.
- 마지막 값이 9876543210 이므로 문자열 길이가 10을 넘을 경우 -1을 출력해준 후 break를 통해서 불필요한 연산 자체를 시행하지 않도록 해줬다.
- 처음에는 1부터 1,000,000 까지 탐색하는 문제인 줄 알고 계산했지만, 틀린 후 문제를 다시 읽어보니 1,000,000 번째 수까지 계산을 해야하는 문제였고, 재귀랑 백트래킹을 통해서 가지치기를 시행하면 풀 수 있을 것 같다 생각해서 ans 라는 변수를 통해서 몇번째 자리에서 돌아오는지, num_length를 통해서 자리수가 몇개인지 등을 체크해서 적절한 값을 number에 할당해줬다.
5. 문제를 푸는데 도움이 되는 지식
- 백트래킹
- 브루트포스
'Python_알고리즘 > Gold V' 카테고리의 다른 글
7576. [Python]토마토 (0) 2023.09.17 1334. [Python]다음 팰린드롬 (0) 2023.09.17 1083. [Python]소트 (0) 2023.09.07 5430. [Python]AC (0) 2023.08.08 2493. [Python]탑 (0) 2023.02.06