백준 2309 일곱난쟁이 완전탐색(코틀린)

문제

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

2309번: 일곱 난쟁이

 

풀이

브루트포스 완전탐색을 묻는 문제입니다.

키의 총합에서 임의의 2명을 뺏을때 총합이 100일때를 출력 하면됩니다.

재귀함수를 사용하여 풀어 보았습니다.

 

 

var result = mutableListOf<Int>()
fun main(args: Array<String>) {

    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    var hum = mutableListOf<Int>()
    repeat(9) {
        hum.add(br.readLine().toInt())
    }

    check2309(0,0, hum)

    result.sort()
    result.forEach {
        if (it != 0) bw.write("$it\n")
    }
    bw.flush()
    bw.close()
}

fun check2309(cnt: Int, idx: Int, hum: MutableList<Int>) {
    if (cnt == 2) {
        if (hum.sum() == 100) {
            if (result.isEmpty()) result.addAll(hum)  // result = hum을 하면 참조값이 들어가기 때문에 이후에 hum가 변경되면 변경된값이 result에 갱신된다.
        }
        return
    }
    for (i in idx until 9) {
        var a = hum.removeAt(i)	// i번째 난쟁이 빼기
        hum.add(i, 0)   // 뺀 난쟁이키를 0으로 변경
        check2309(cnt + 1, i + 1, hum)
        hum.removeAt(i)
        hum.add(i, a)	// 난쟁이 다시 추가하여 초기화, 다음 난쟁이 검사
    }
}