[백준] 1174_줄어드는 수 (Python)

1174__줄어드는 수 (Python)

0. 출처

• 유형 : 백트래킹 (gold 5)
• 링크 : 1174_번: 줄어드는 수

1. 기록

• 22/04/10 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 예제 입력과 예제 출력을 보고 뭔말인지 도저히 모르겠음
>> 문제 이해 함
>> 문제 조건에 맞는 1번째로 가장 작은수는 0
>> 2번째로 가장 작은 수는 1
>> 3번째로 가장 작은 수는 2
>> ...
>> 10번째로 가장 작은 수는 9
>> 11번째로 가장 작은 수는 10
>> 12번째로 가장 작은 수는 20

>> 그래서 어떻게 풀건데? 
>> 마지막 값 > 현재 값 경우, 재귀 진행하여 감소하는 수를 만들어 준다.
>> 감소하는 수를 정렬한다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

n = input()
arr = list()
result = list()

def dfs():
    if len(arr) > 0:
        result.append(int("".join(map(str, arr))))

    for i in range(0, 10):
        if len(arr) == 0 or arr[-1] > i:  # 마지막 값이 더 큰 경우
            arr.append(i)
            print(arr)
            dfs()
            arr.pop()

try:
    dfs()
    result.sort()
    print(result[n - 1])
except:
    print(-1)

(4) 정리

처음에 문제가 이해가 안가서 답안 코드에 1부터 하나하나 집어넣고 이해했다.

문제 이해력을 길러야겠다.

(5) 참고

참고 풀이