1038. [Python]감소하는 수

1. 문제

 

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

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. 문제를 푸는데 도움이 되는 지식

 

• 백트래킹
• 브루트포스