백준 1038 감소하는 수

출처: www.acmicpc.net/problem/1038

분류: 완전탐색

---

접근방식

n번째 감소하는 수를 찾는 문제였습니다. 

한 자리 수는 모두 감소하는 수이며, 작은 수부터 찾아줘야 합니다. 

감소하는 수는 이런 식으로 진행됩니다.

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, 40, 41, 42, 43, 50, ... ]

규칙을 생각해보면 마지막 수는 마지막 앞자리 수보다 작아야 하니
앞자리 수가 4라면 마지막에 올 수 있는 수는 0, 1, 2, 3 이 됩니다.

그리고 마지막 자리를 제외한 수도 무조건 감소하는 수가 되어야 합니다.
감소하는 수 54 다음에 540, 541, 542, 543 이 올 수 있지만
44는 감소하는 수가 아니기 때문에 440, 441 등은 될 수가 없습니다.

즉 감소하는 수에서 다음 감소하는 수가 파생됩니다.

감소하는 수 1을 가지고 10을 만들 수 있고

감소하는 수 42를 가지고 420, 421을 만들 수가 있습니다.

저는 이런 성질을 이용해서 처음에 0~9까지 한 자리 감소하는 수를 미리 넣어놓고

인덱스를 증가시키면서 해당 인덱스의 감소하는 수를 이용해서 만들 수 있는
감소하는 수를 배열에 추가시켜주는 방식으로 해결했습니다.

 

마지막으로 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 에서

몇 개를 뽑으면 거기서 만들 수 있는 감소하는 수는 무조건 하나로 고정됩니다.

감소하는 수의 각 자리 수는 중복되지 않기 때문이죠!

임의로 [0, 3, 5] 를 뽑았다면 여기서 만들 수 있는 감소하는 수는 무조건 530이 됩니다. 

따라서 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 에서 만들 수 있는 감소하는 수의 개수는 2^10 - 1인 1023개가 됩니다.

문제의 조건에 따라 이를 넘어서는 n이 들어오면 -1을 출력하도록 예외처리까지 해준다면 문제를 해결할 수 있습니다. 

 

이를 이해하면 감소하는 수의 조합 1023개를 다 뽑은다음 정렬시켜버리는 방법으로도 해결할 수 있습니다 *_*
(바킹독님의 풀이)

 

해결방법

let n = Int(readLine()!)!

func solution() {
    guard n >= 10 else { print(n); return }
    guard n < 1023 else { print(-1); return }
    
    var decreases = (0...9).map { $0 }
    var target = 0
    
    while true {
        let before = decreases[target] % 10
        for num in 0..<before {
            decreases.append(decreases[target] * 10 + num)
            
            if n+1 == decreases.count {
                print(decreases[n])
                return
            }
        }
        target += 1
    }
}

solution()

 

배운점

해결하는 데 한참이 걸렸다 ㅠㅠ

완탐은 될 거 같은데 안 되고 될 거 같은데 어떻게 해야되지..? 라는 생각으로 괴롭힌다...

특히 완탐을 풀 때 멘탈이 더 바사삭 되는 것 같다. 😢