백준 1170번: 리모컨 (Kotlin)

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

1107번: 리모컨

 

풀이

골드5였는데 정말 정말 어려웠다.

지금껏 풀어봤던 문제들이랑 사고방식이 전혀 다르다는 느낌이 들었다. 구현이랑 완전 탐색 문제 경험이 부족한걸까.

 

처음에 그리디적으로 접근했는데 분기문이 감당이 안됐다. 브루트 포스 유형이란걸 알고나서도 어떻게 풀지 쉽게 떠오르지 않았다. 다른 분들 풀이를 참고했는데, 풀면서 멘탈이 나갔는지 처음엔 설명을 봐도 이해가 안됐다..ㅋㅋㅋ

 

알고나니까 컨셉은 간단했다!

버튼을 눌러서 한번에 이동할 수 있는 채널을 모두 구하는 것이다.

그러면, 모든 (이동 가능한 채널 i의 자리수) + (i에서 목표 채널 N(target)까지 거리) 중 최소 값과 100에서 N까지 +, -로 가는 거리 중 최소 값이 답이 된다.

 

순서

1. 고장난 버튼의 개수를 확인한다. 만약 버튼이 전부 고장났다면, +, -로 이동하는 횟수가 정답이다
2. 1개라도 고장나지 않았다면, 0 <= i <= 900,000에 대해, +, - 없이 i로 한번에 이동할 수 있는 수들을 확인한다.
3. 이동 가능한 수들의 i로 직접 버튼 클릭 + 절대값(N - i) 중 최소값을 구한다.
4. 위에서 구한 최소값과 100에서 N으로 곧장 가는 절대값(N - 100) 중 작은 값이 답이 된다. (N = 101 같은 케이스 고려)

 

900,000까지 탐색하는 이유는 다음과 같다.

문제가 원하는 답은 아래 3가지 경우 중 최소값이다

1. 100에서 N까지 바로 가는 경우
2. 100에서 i <= N인 i를 거쳐 가는 경우 (왼쪽에서 오른쪽)
3. 100에서 i > N인 i를 거쳐 가는 경우(오른쪽에서 왼쪽) 

그리고 2, 3번의 경우

• 왼쪽에서 오른쪽으로 가는 최대 횟수는 N = 500,000이고 고장나지 않은 버튼이 0인 경우의 100 -> 500,000인 499,900번,
• 오른쪽에서 왼쪽으로 가는 최대 횟수는 고장나지 않은 버튼이 0과 9인 경우의 100 -> 900,000 -> 500,000인 400,006번이다. 그 이상의 수를 확인해봤자 499,900번을 넘기 때문에 확인하지 않아도 된다.

 

좀 더 간단하게는 왼쪽 -> 오른쪽 최대 값이 약 50만이기 때문에 최대 숫자를 50만 + 50만 = 100만으로 설정해서,

0 <= i <= 1,000,000을 탐색할 수 있다!

 

코드1

import java.io.*
import java.util.StringTokenizer
import kotlin.math.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val target = readLine().toInt()
    val brokenCount = readLine().toInt()
    val broken = BooleanArray(10)

    // 버튼이 망가졌으면 true, 아니면 false
    if (brokenCount > 0){
        val st = StringTokenizer(readLine())
        repeat(brokenCount) {
            broken[st.nextToken().toInt()] = true
        }
    }

    // 전부 고장났으면 +, -로만 이동하는 게 정답
    if (brokenCount == 10 || target == 100) {
        print(abs(target - 100))
        return
    }

    // target = 101과 같은 경우 고려
    var minClicked = abs(target - 100)
    
    for (i in 0 until 900_000) {
        val number = i.toString()

        // i로 번호를 직접 입력해서 갈 수 있는지 확인한다.
        if (isReachable(number, broken)){
            val numberToTarget = abs(i - target) // i에서 target으로 +나-로 이동하는 횟수
            minClicked = min(minClicked, number.length + numberToTarget)
        }
    }

    print(minClicked)
}

// 각 자리수 중 하나라도 망가진 번호가 있으면 직접 거쳐갈 수 없다.
fun isReachable(target: String, broken: BooleanArray): Boolean {
    target.forEach{ ch ->
        val number = ch - '0'
        if (broken[number]) return false
    }

    return true
}

 

코드2 (각 자리수 확인할 때 문자열이 아닌 정수로 처리하는 버전)

import java.io.*
import java.util.StringTokenizer
import kotlin.math.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val target = readLine().toInt()
    val brokenCount = readLine().toInt()
    val broken = BooleanArray(10)

    if (brokenCount > 0){
        val st = StringTokenizer(readLine())
        repeat(brokenCount) {
            broken[st.nextToken().toInt()] = true
        }
    }

    if (brokenCount == 10 || target == 100) {
        print(abs(target - 100))
        return
    }

    var minClicked = abs(target - 100)
    for (i in 0 until 900_000) {
        val clickCount = getClickCount(i, broken)
        if (clickCount > 0){
            val iToTarget = abs(i - target)
            minClicked = min(minClicked, clickCount + iToTarget)
        }
    }

    print(minClicked)
}

fun getClickCount(target: Int, broken: BooleanArray): Int {
    var count = 0
    var targetNumber = target

    while(true) {
        val button = targetNumber % 10
        if (broken[button]) {
            return 0
        }

        count++
        targetNumber /= 10
        if (targetNumber == 0) break
    }

    return count
}