백준 2138 전구와 스위치

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

N개의 전구가 있고 i번째 스위치를 켜면 i번째 전구와 그 양 옆 전구가 켜진 상태면 꺼지고 꺼진 상태면 켜지게 된다.

최초 전구 상태에서 최소한의 스위치를 눌러 목표 상태로 만들려고 할 때 그 횟수를 출력하는 문제이다.

문제에 접근할 때 중요한 정보가, 최소한의 스위치를 누르는 것이라고 생각하였다.

그것은 즉 각 스위치를 최대 1번까지만 누르는 것이다. 예를 들어 보자

00000 상태가 있다.

1번 스위치를 한 번 눌러 11100으로 만드는 것과 0번 스위치를 2번 누르고 1번 스위치를 한 번 눌러 11100으로 만드는 것은 같은 결과를 반환한다.

따라서 스위치는 0번 또는 1번만 누르는 경우에 최소한의 횟수를 보장한다.

또한 스위치를 누르는 순서는 결과와 관련이 없다.

1번 스위치를 누른 후 2번 스위치를 누르는 것과 2번을 누른 후 1번을 누르는 것은 같은 결과를 반환한다.

이 두 가지 정보를 가지고 접근한 결과, 알고리즘을 생각해내었다.

최초 상태가 00000이고 목표 상태가 10000이라고 해 보자.

최초 상태에서 0번 위치의 전구의 상태를 바꿀 수 있는 스위치는 0번과 1번 스위치이며, 최초 상태의 목표 전구는 켜진 상태(1)이다.

그럼 케이스를 나눌 수 있다.

1. 0번 스위치를 누른 경우 - 0번 전구는 켜져 1로 바뀌며, 목표 상태와 동일하다. 따라서 1번 스위치는 누르지 않아야 한다.

2. 0번 스위치를 누르지 않은 경우 - 0번 전구는 그대로 꺼진 상태 0으로 있으며, 목표 상태와 다르다. 따라서 1번 스위치는 꼭 눌러야 한다.

위는 0번 전구의 상태와 목표 상태와 다를 경우이지만, 같은 경우에도 비슷하다.

0번 스위치를 누른 경우 1번 스위치도 눌러야 하며, 0번 스위치를 누르지 않은 경우 1번 스위치도 누르지 않아야 한다.

즉 0번 스위치를 눌렀냐 누르지 않았냐에 따라 1번 스위치의 동작을 강제하는 것이다.

그럼 1번 스위치의 동작에 따라 2번 스위치도 목표 상태에 따라 동작이 강제되게 된다.

제대로 예시를 들어 생각해보자.

최초: 0000
목표: 1011

1. 0번째 스위치를 누르지 않은 경우

• 목표의 0번째 전구가 1이므로 1번째 스위치를 누른다 (현재 1110)
• 목표의 1번째 전구가 0이므로 2번째 스위치를 누른다 (현재 1001)
• 목표의 2번째 전구가 1이므로 3번째 스위치를 누른다 (현재 1010)
  1010과 1011은 다르므로 0번 스위치를 누르지 않으면 목표상태가 될 수 없다.

2. 0번째 스위치를 누른 경우 (현재 1100)

• 목표의 0번째 전구가 1이므로 1번째 스위치를 누르지 않는다
• 목표의 1번째 전구가 0이므로 2번째 스위치를 누른다 (현재 1011)
• 목표상태이므로 나머지 스위치는 누르지 않는다. 2회 누르기로 목표상태.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val src1 = readLine().toCharArray()
    val src2 = src1.clone()
    val dest = readLine().toCharArray()

    var answer = -1
    var pushCnt = 0
    // without push 0
    for(i in 1 until src1.size){
        if(src1[i - 1] == dest[i - 1]) continue
        else {
            pushButton(src1, i)
            pushCnt++
        }
    }
    if(isArraySame(src1, dest)){
        if(answer == -1 || (answer != -1 && answer > pushCnt))
            answer = pushCnt
    }

    // with push 0
    pushCnt = 1
    pushButton(src2, 0)
    for(i in 1 until src2.size){
        if(src2[i - 1] == dest[i - 1]) continue
        else {
            pushButton(src2, i)
            pushCnt++
        }
    }
    if(isArraySame(src2, dest)){
        if(answer == -1 || (answer != -1 && answer > pushCnt))
            answer = pushCnt
    }

    print(answer)
}

fun pushButton(arr: CharArray, pos: Int){
    when(pos){
        0 -> {
            arr[0] = if(arr[0] == '0') '1' else '0'
            arr[1] = if(arr[1] == '0') '1' else '0'
        }
        arr.size - 1 -> {
            arr[arr.size - 1] = if(arr[arr.size - 1] == '0') '1' else '0'
            arr[arr.size - 2] = if(arr[arr.size - 2] == '0') '1' else '0'
        }
        else -> {
            arr[pos] = if(arr[pos] == '0') '1' else '0'
            arr[pos - 1] = if(arr[pos - 1] == '0') '1' else '0'
            arr[pos + 1] = if(arr[pos + 1] == '0') '1' else '0'
        }
    }
}

fun isArraySame(src: CharArray, dest: CharArray): Boolean{
    for(i in src.indices){
        if(src[i] != dest[i]) return false
    }
    return true
}