백준 1107 리모컨

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

분류: 완전 탐색

---

접근방식

돌고돌아 결국 순수한 완전탐색으로 해결한 문제입니다.

고장난 숫자 버튼이 주어질 때 원하는 채널을 만들기 위해 필요한 조작 횟수를 구하는 문제입니다.

조정할 수 있는 채널 중에서 원하는 채널과 가장 가까운 채널로 가서 + 혹은 - 로 조작하면 최소의 수를 구할 수 있... 을줄 알았으나,

생각보다 간단한 문제는 아니었습니다.

 

가장 가까운 채널을 어떻게 만들 것인가,

"처음엔 수어진 숫자의 각 자리 마다 위, 아래로 가까운 수를 뽑으면 가장 가까운 수가 되겠구나." 
라고 생각하고 접근했습니다.

5000
2
5 0

이렇게 주어지면, 5 와 0을 피해 가장 가까운 각 자리 수를 up, down으로 만들면,

밑으로 가장 가까운 수는 4999
위로 가장 가까운 수는 6111 
이 되므로 4999 로 가서 +1 을 해주면 5번 만에 만들 수가 있습니다.

그리고 만약 +해서 10이 넘어가면 % 연산으로 0으로 만들어주고,
- 해서 0보다 작아지면 9로 만들어주도록 처리해줬습니다.
이렇게 하면 위 아래가 같은 수가 될 수 있겠지만 그게 최선일거다! 라고 생각했죠.

하지만 다음은 어떨까요?

1555
8
0 1 3 4 5 6 7 9

이 경우 제가 위에서 사용한 방법을 사용하면
위로 2888
밑으로 8222 가 나와버립니다 ;;

완전 잘못 생각했었죠 ㅠㅠ
잘 처리 해줘서 2222를 만들 수도 있겠으나 문제는 2222도 정답이 아닙니다.

2222 - 1555 = 677 에 2222를 누르는 4를 더해서 671 이지만,

이 경우 가장 최소 값은 

1555 - 888 = 667 에 888을 누르는 3을 더해서 670 입니다.

완전탐색

이 경우 최대 입력이 500000 이므로 6자리까지 숫자를 만들어 가면서 각각의 경우를 다 계산해서 최소값을 비교해도 50만 정도로 계산할 수가 있습니다. 

저 반례를 보고 아 안되겠다 싶어서 그래서 그냥 완전탐색으로 해결했습니다.

 

하지만 포스팅하면서 생각해보니 처음에 접근했듯이 위 아래 최소값을 찾아서 계산해줄 수도 있을 것 같네요.
실제로 그런식으로 저보다 훨씬 빠르게 계산하신 분들도 계시는군요..!

 

해결방법

let strN = readLine()!
let n = Int(strN)!
var failures = Set<Int>()
if Int(readLine()!)! != 0 {
    failures = Set<Int>(readLine()!.split(separator: " ").map({Int($0)!}))
}
var minOrder = abs(n - 100)

func makeAllNumbers(num: String) {
    if num.count >= 6 {
        return
    }
    
    for i in 0..<10 {
        if failures.contains(i) {
            continue
        } else {
            let orderCount = abs(n - Int(num + String(i))!) + num.count+1
            minOrder = min(minOrder, orderCount)
            makeAllNumbers(num: num+String(i))
        }
    }
}
makeAllNumbers(num: "")
print(minOrder)

 

배운점

완전 탐색이 가능하면 그냥 완전 탐색으로 푸는 것도 좋은 방법!

여러 케이스들을 잘 고려하기는 참으로 어렵다..