백준 1208번: 부분수열의 합2 (Kotlin)

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

1208번: 부분수열의 합 2

 

생각 과정

1. 문제 재해석: 앞, 뒤 순서를 만족시키되 연속 상관없이 숫자들을 선택해서 더했을 때 값이 S가 되는 경우의 수를 구하시오
2. 모든 경우의 수를 확인한다면 2^40가지가 나오기 때문에 시간 내에 해결할 수 없다.
3. 수열을 절반으로 나누면 2^20가지이므로 각각의 부분합은 모두 구할 수 있다.
4. 합 S가 정해져 있으므로, 한쪽 부분합 배열에서 숫자를 선택하면 다른 한쪽에 존재하는지 확인할 숫자가 정해진다.
5. 한쪽의 부분합을 순회하면서 다른 한쪽에 원하는 숫자가 있는지 찾는다 -> 해싱, 투포인터, upper_bound - lower_bound를 사용해서 해결할 수 있다.
6. 피자 판매(https://www.acmicpc.net/problem/2632)와 비슷한 문제였다. (피자 판매 포스팅: https://best-human-developer.tistory.com/60) 

 

코드 (해싱)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

lateinit var numbers: IntArray
val leftSumCount: MutableMap<Int, Int> = HashMap()
var goal = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, mGoal) = readLine().split(" ").map(String::toInt)
    val st = StringTokenizer(readLine())
    numbers = IntArray(n) { st.nextToken().toInt() }
    goal = mGoal

    recordLeftSum(0, 0)
    val answer = countAnswer(n / 2, 0)

    if (goal == 0) print(answer - 1) // 각 구간에서 아무것도 뽑지 않아서 0이 된 경우를 뺀다
    else print(answer)
}

// 왼쪽 절반 구간에서 구할 수 있는 모든 부분수열의 합을 key, 개수를 value로 Map에 저장한다
fun recordLeftSum(idx: Int, sum: Int) {
    if (idx >= numbers.size / 2) {
        leftSumCount[sum] = leftSumCount.getOrDefault(sum, 0) + 1
        return
    }

    recordLeftSum(idx + 1, sum)
    recordLeftSum(idx + 1, sum + numbers[idx])
}

// 오른쪽 구간 부분수열의 합(rightSum)을 모두 구해서,
// 자신과 합했을 때 목표 숫자를 만드는 leftSum의 개수를 Map에서 찾아서 반환한다
fun countAnswer(idx: Int, sum: Int): Long {
    if (idx >= numbers.size) {
        return leftSumCount.getOrDefault(goal - sum, 0).toLong()
    }

    return countAnswer(idx + 1, sum) + countAnswer(idx + 1, sum + numbers[idx])
}