[백준][2309][KOTLIN] 일곱 난쟁이

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

2309번: 일곱 난쟁이

문제 풀이

1. 처음에 접근할 때 9명의 난쟁이 중 7명을 뽑아서 합을 구하는 것으로 접근했다.

2. 1번과 같이 접근하기 위해서 백트래킹을 이용한 조합을 통해서 7명의 배열을 구하고 합이 100인 배열을 구했다.

3. 위와 같이 할 경우 경우의 수가 너무 많고 각 배열의 합을 다시 확인해야 해서 비효율적이다.

4. 9명의 전체 키의 합을 구한 뒤 이중 for 문을 이용하여 2명의 키를 뺀 합이 100인 경우를 찾아서 리스트를 오름차순으로 정렬하여 출력한다.

5. 4번과 같이 할 경우 최대 9C2 의 경우의 수만큼 탐색하여 답을 구할 수 있다.

6. 4번의 탐색해서 이중 for 문이므로 조건에 해당하여 답을 출력하고 빠져나올 때 이중 for 문을 빠져 나올 수 있도록 label 을 달아준다.

코드

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val dwarf = mutableListOf<Int>()
    repeat(9) {
        dwarf.add(br.readLine().toInt())
    }

    val sum = dwarf.sum()

    loop@ for (i in 0..7) {
        for (j in (i + 1)..8) {
            val first = dwarf[i]
            val second = dwarf[j]

            if (sum - (first + second) == 100) {
                println("$i, $j, $first, $second")
                dwarf.remove(first)
                dwarf.remove(second)
                dwarf.sort()

                dwarf.forEach { d ->
                    println(d)
                }
                break@loop
            }
        }
    }
}