[백준] (Swift) 1107번 - 리모컨 (완전탐색, 두번째 오답노트)

🟠 문제

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

1107번: 리모컨

 

🟠 나의 풀이

먼저 문제가,,, 일단 골드라는 것에 덜컥 겁이 났지만,, 예전에 한번 풀어봤던 문제이기에 조금씩 기억이 났다. 알고리즘 문제 풀면서 이거 백프로 다음에 기억못함 ㅋㅋㅋ 이러고 풀지만, 은근히 기억이 난다! 

우선, 위와 같은 경우에는 세가지의 방법으로 채널을 이동할 수 있다.

1. +, - 버튼으로만 완벽하게 이동
2. 숫자버튼이 고장나지 않아서, 숫자버튼으로만 이동
3. 숫자버튼이 고장난 것이 생겨서 가까운 어디론가 이동 해서 +와 -로 추가이동

이렇게 세가지 경우로 생각할 수 있다.

문제의조건을 보면, 이동하려고하는 채널N은 500000와 같거나 작은수로 제시되지만, 이동할 수 있는 채널은 무한대다. 여기서 단순하게 500000까지 범위를 잡으면 되겠지 했다가 큰코다친 사람이 바로 나다!! 😃

채널이 무한대로 있다고 언급해준 이유는 무엇일까? 이동할 수 있는 범위가, 조건에서 주어진 500000보다 넘어갈 수 도 있다는 뜻이다.
예시로 살펴보자.

채널 500000으로 이동한다고 할 때,
1에서 500000으로 이동하는 것보다, 999000에서 500000으로 이동하는 것이 더 적은 버튼을 누르고 이동할 수 있다.

이러한 경우처럼, 현재 수보다 큰 수를 눌러서 채널을 이동했을때 더 효율적일 수 있다. 그러므로, 범위를 최소 1000000까지 봐야한다. (우리가 돌릴 수 있는 채널은 50만 이므로!)

다시 그럼 돌아와서, 위에서 적은 3가지 방식을 for문을 이용해서 완전탐색으로 풀어보자

 

🟠 정답코드

• solution() : 메인함수
• pressCloseNumber() : 숫자버튼을 누르는 횟수를 세어주는 함수
• for문을 돌린 이유 : 0번부터 1000000까지 전부 눌러보는 것. 이동해야하는 수가 100이어도, 1000이어도, 1000000이어도 모든 수를 탐색한 후, 가장 최소로 눌려진 버튼 횟수를 출력할 수 있도록 한다.
• 처음 minCnt에 +와-로만 이동가능한 횟수를 넣어준다. abs(이동하려는채널n - 시작채널100)
• for 문을 이용해서 최소값을 찾아준다. 
  • 최소값(+와 -만 눌러서 돌렸을때 vs. 채널1로 돌리고 +-로 조절한 횟수)
  • 위에서 도출된 최솟값 vs. 채널2로 돌리고 +-로 조절한 횟수
  • 위에서 도출된 최솟값 vs. 채널3으로 돌리고 +-로 조절한 횟수 
  • .....
  • 100만까지 진행

import Foundation

private func solution() {
    let n = Int(readLine()!)!
    let m = Int(readLine()!)!
    var brokenBtn = [Int]()
    if m != 0 {
        brokenBtn = readLine()!.split(separator: " ").map { Int($0)! }
    }

    // +-로만 이동하는 횟수
    var minCnt = abs(n - 100)

    // 숫자버튼을 눌러서 이동하는 경우 전부 테스트
    // 숫자버튼으로 i를 눌렀을 때랑, +-로만 이동할때랑 비교해주는 부분
    for i in 0...1000000 {
        let pressNumButton = pressCloseNumber(n: i, brokenBtn: brokenBtn)

        if pressNumButton > 0 {
            let pressNumAndPlusMinus = abs(n - i) // 채널 i로 이동했으니까, 거기서 +-눌러주는 횟수
            minCnt = min(minCnt, pressNumAndPlusMinus + pressNumButton)
        }
    }

    print(minCnt)
}

private func pressCloseNumber(n: Int, brokenBtn: [Int]) -> Int {
    var n = n

    if n == 0 {
        if brokenBtn.contains(n) {
            return 0
        } else {
            return 1
        }
    }

    var buttonPressCnt = 0
    while n > 0 {
        if brokenBtn.contains(n % 10) {
            return 0
        }

        n /= 10
        buttonPressCnt += 1
    }
    return buttonPressCnt
}

solution()