[백준 1107번] [Kotlin] 리모컨

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

1107번: 리모컨

 

난이도 : 골드 5
태그 : 브루트포스

 

---

1. 설명

 

이동하려는 채널(target)을 시작으로,

 

윗 방향(upperBtn)과 아랫 방향(lowerBtn) 채널을 하나씩 체크해 나가며 풀 수 있습니다.

 

둘중 하나라도 고장나지 않은 버튼들로 이동할 수 있는 채널일때 해당 값을 출력하면 됩니다.

 

---

2. 소스코드

 

      

      

      

    
    

      <code />
    
val br = BufferedReader(InputStreamReader(System.`in`))

val target = br.readLine().toInt()
val n = br.readLine().toInt()

val usePlusAndMinus = abs(target - 100) // + - 버튼을 사용해서 이동할경우

if (n == 0) {
    println(min(usePlusAndMinus, target.toString().length))
    return
}

 

usePlusAndMinus는 +- 버튼만을 이용해 이동한 경우입니다.

고장난 버튼이 없을 경우, +- 를 통해 이동한 경우와, 해당 채널 버튼을 입력한 횟수 중 작은 것을 출력하고

프로그램을 종료하면 됩니다.

 

      

      

      

    
    

      <code />
    
val st = StringTokenizer(br.readLine(), " ")
disableBtn = Array(n) { " " }
for (i in 0 until n) disableBtn[i] = st.nextToken()

stringTokennizer 를 통해 고장난 버튼들을 입력받았습니다.

 

 

      

      

      

    
    

      <code />
    
fun isAble(c: Int): Boolean {
    var channel = c.toString()

    for(i in channel) {
        if(i.toString() in disableBtn) {
            return false
        }
    }
    return true
}

해당 채널이 고장난 버튼들로 이동할 수 있는지 판단하는 메소드 입니다.

참고로 고장난 버튼들(disableBtn)은 전역변수 입니다.

 

 

      

      

      

    
    

      <code />
    
var cnt = 0


var upperBtn = target
var lowerBtn = target


while (true) {

    if (cnt + upperBtn.toString().length >= usePlusAndMinus && cnt + lowerBtn.toString().length >= usePlusAndMinus) {
        println(usePlusAndMinus)
        break
    }

    if (isAble(lowerBtn) && lowerBtn >= 0) {
        println(cnt + lowerBtn.toString().length)
        break
    }

    if (isAble(upperBtn)) {
        println(cnt + upperBtn.toString().length)
        break
    }

    upperBtn++
    lowerBtn--
    cnt++
}

 

함수의 메인 로직입니다.

 

이동하려는 채널(target)으로 부터,

채널을 하나씩 올리는 경우와 하나씩 내려 둘중 하나라도

해당 채널이 고장난 버튼들로 이동 가능할 경우 해당 채널을 출력하고, 반복문을 빠져나옵니다.

 

혹은, 초기 채널(100)에서 +-를 이용해 이동했을때 버튼 누르는 횟수를 초과했을 경우,

+-를 사용한 버튼 누른 횟수를 출력하고 반복문을 빠져나옵니다.

 

 

 

      

      

      

    
    

      <code />
    
if (isAble(lowerBtn) && lowerBtn >= 0) {
    println(cnt + lowerBtn.toString().length)
    break
}

if (isAble(upperBtn)) {
    println(cnt + upperBtn.toString().length)
    break
}

다만, 탐지 범위에 하한선(lowerBtn)이 상한선(upperBtn)보다 먼저 체크해야 합니다.

 

하한선의 경우, 숫자가 계속 낮아지므로,

채널의 자릿수가 더 적어질 수 있기 때문입니다.

 

ex> 1010번 채널로 이동 하려는데, 하한선이 990번, 상한선이 1030번으로 동시에 도달했다고 가정합니다.

이럴 경우, 하한선은 버튼 20번과, 990을 눌러 20+3 = 23번의 버튼을 누르게 됩니다.

하지만 상한선은 20번의 버튼과, 1030번을 눌러 20+4 = 24번의 버튼을 누르게 되어

 

하한선을 먼저 검사하는 것이 필요합니다.

 

3. 전체 소스코드

      

      

      

    
    

      <code />
    
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.abs
import kotlin.math.min

lateinit var disableBtn: Array<String>

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    val target = br.readLine().toInt()
    val n = br.readLine().toInt()

    val usePlusAndMinus = abs(target - 100) // + - 버튼을 사용해서 이동할경우

    if (n == 0) {
        println(min(usePlusAndMinus, target.toString().length))
        return
    }

    val st = StringTokenizer(br.readLine(), " ")
    disableBtn = Array(n) { " " }
    for (i in 0 until n) disableBtn[i] = st.nextToken()

    var cnt = 0


    var upperBtn = target
    var lowerBtn = target


    while (true) {

        if (cnt + upperBtn.toString().length >= usePlusAndMinus && cnt + lowerBtn.toString().length >= usePlusAndMinus) {
            println(usePlusAndMinus)
            break
        }

        if (isAble(lowerBtn) && lowerBtn >= 0) {
            println(cnt + lowerBtn.toString().length)
            break
        }

        if (isAble(upperBtn)) {
            println(cnt + upperBtn.toString().length)
            break
        }

        upperBtn++
        lowerBtn--
        cnt++
    }
}

fun isAble(c: Int): Boolean {
    var channel = c.toString()

    for(i in channel) {
        if(i.toString() in disableBtn) {
            return false
        }
    }
    return true
}

---

4. 후기

 

모든 경우의 수를 탐색하는 브루트포스 알고리즘을 사용하여 풀 수 있었던 문제였습니다.

 

문제의 접근 자체는 금방 떠올랐지만... 여러 반례들을 생각하지 못해 '틀렸습니다' 문구를 꽤나 많이 봤던 문제였습니다.

 

리모컨이 고장나 버튼을 수없이 누를 수도 있는 수빈이에게 박수를.