백준 17610 양팔저울 Kotlin (완전 탐색)

문제 출처 : https://www.acmicpc.net/problem/17610

17610번: 양팔저울

문제

무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고 그 무게가 각각 {1, 2, 6}이면, S = 9이고, 양팔 저울을 한번만 이용하여 1부터 S사이 모든 정수에 대응하는 물을 다음과 같이 그릇에 담을 수 있다. 여기서, X는 그릇에 담는 물의 무게를 나타내고, □는 그릇을 나타낸다.

만약 추의 무게가 {1, 5, 7}이면 S = 13이 되고, 양팔저울을 한 번만 사용하여 그릇에 담을 수 있는 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이다. 즉, 1부터 S사이 수 가운데 9와 10에 대응하는 무게의 물을 그릇에 담는 것은 불가능하다.

k(3 ≤ k ≤ 13)개 추 무게 g1, g2, ..., gk가 주어질 때, 1부터 S사이에 있는 정수 중, 양팔 저울을 한번만 이용하여서는 측정이 불가능한 경우의 수를 찾는 프로그램을 작성하고자 한다.

입력

입력의 첫 줄에는 추의 개수를 나타내는 정수 k(3 ≤ k ≤ 13)가 주어진다. 다음 줄에는 k개의 정수 gi(1 ≤ gi ≤ 200,000)가 공백으로 구분되어 주어지는데 이는 각 추의 무게를 나타낸다.

출력

1부터 S(추 무게의 합) 사이에 있는 정수 중, 양팔 저울을 한번만 이용해서는 측정이 불가능한 경우의 수를 출력한다.

알고리즘 분류

• 브루트포스 알고리즘

풀이

완전 탐색 문제이다.

아니 이제 "완전 탐색 문제이다"가 아니라 "완전 탐색으로 접근했다."로 바꿔야겠다.

문제마다 다양한 접근이 가능하기에..

 

완전 탐색으로 접근했다.

 

혹시 이 문제를 풀다가 막혀서 검색했다면 아래 핵심만 보고 다시 스스로 푸는 것을 추천한다.

탐색의 가지는 3가지가 있다.

1. 현재 추를 올리지 않는 경우

2. 현재 추를 올리는 경우

3. 현재 추를 반대쪽에 올리는 경우 (-), a-b나 b-a나 우리는 양수만 필요하므로 Math.abs하면 똑같다.

왜 이 3가지인지, 이 3가지를 기반으로 완전 탐색을 어떻게 구현하면 좋을지 생각하면 쉽게 풀 수 있다.

 

본인은 재귀를 이용하여 이를 해결했다.

저 3가지 경우 외엔 딱히 설명할 게 없다.

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

lateinit var isExisted: BooleanArray

fun solve(idx: Int, weight: Int, input: List<Int>) {
    
    if (idx >= input.size) {
        isExisted[weight] = true
        return
    }
    solve(idx + 1, weight, input)
    solve(idx + 1, weight + input[idx], input)
    solve(idx + 1, Math.abs(weight - input[idx]), input)
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    val k = getInt()
    val input = getIntList()
    val max = input.maxOf { it } * k
    val sum = input.sum()
    isExisted = BooleanArray(max + 1)
    var answer = 0

    //solve
    solve(0, 0, input)
    for (i in 1..sum) {
        if (!isExisted[i]) answer++
    }
    //output
    write("$answer")

    close()
}