백준 18114 블랙 프라이데이 Kotlin (이분 탐색)

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

18114번: 블랙 프라이데이

문제

서강 백화점이 블랙 프라이데이를 맞아서 특별 이벤트를 진행한다. 백화점에서 제시하는 양의 정수의 무게 C에 딱 맞게 물건들을 가져오면 전부 만 원에 판매하는 이벤트이다.

선택할 수 있는 물건은 최대 3개까지이고, 같은 물건을 중복 선택하는 것은 불가능하다. 그리고 백화점에서 판매하는 물건들의 무게는 모두 다르다.

예를 들어, 백화점에서 판매하고 있는 물건 5개의 무게가 각각 1, 2, 3, 4, 5일 때, C가 5라면 {2, 3} 또는 {5}에 해당하는 물건의 조합을 만 원에 구매할 수 있다.

판매하는 물건 N개의 양의 정수의 무게가 각각 주어질 때, 만 원에 구매할 수 있는 조합이 있는지 출력하라.

입력

첫 번째 줄에 물건의 개수 N과 제시하는 무게 C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ C ≤ 108, N과 C는 양의 정수)

다음 줄에는 N개의 물건 각각의 무게 w가 공백으로 구분되어 주어진다. (1 ≤ w ≤ 108, w는 양의 정수)

출력

문제의 조건을 만족하는 조합이 있으면 1, 그렇지 않으면 0을 출력한다.

알고리즘 분류

• 브루트포스 알고리즘
• 정렬
• 이분 탐색

풀이

이분 탐색 문제이다.

처음엔 연속적으로 선택해야 하는 줄 알고 투 포인터로 풀었다가 틀렸다.

해당 문제는 연속적으로 선택하지 않아도 되는 조합을 찾아야 하므로 다른 방법이 필요하다.

우선 완전 탐색이 가능한지 확인하자.

3개를 고르는 것만 해도 5000^3으로 불가능하다.

뭔가 이분 탐색으로 해결할 수 있을 것 같다. 하지만 3개를 선택해야 하는데 어떻게 이분 탐색을?

한 개만 선택할 수 있게 만들어 주면 된다.

예를 들어 3개를 선택해야 하는 경우 2개를 미리 선택해 두고 나머지 하나를 이분 탐색으로 찾으면?

x+y+z가 c인 조합이 있는지 찾아야 하는데, x,y를 미리 선택해 두고 이분 탐색으로 z만 찾으면?

5000^2 * log5000 으로 가능하다.

최대 3개를 선택하는 문제이므로 

3개를 선택하는 경우 (2개 미리 선택 후 나머지 이분 탐색)

2개를 선택하는 경우 (1개 미리 선택 후 나머지 이분 탐색)

1개를 선택하는 경우 (0개 미리 선택 후 나머지 이분 탐색)

위의 말을 보면 나머지 이분 탐색이란 말이 조금 헷갈릴 수 있다.

1개 미리 선택 후 나머지 이분 탐색하면 결국 이분 탐색에서 두 개의 값을 찾아야 하는 거 아니야??

1개만 미리 선택한다는 것은 입력으로 주어진 어떤 값을 하나 선택하고, 나머지 하나는 선택 안 함(0 값), 나머지 하나는 이분 탐색으로 찾는다.

즉 이분 탐색으로 찾을 값을 x,y,z중 z라 한다면

(x,y,z) = 3개 선택하는 경우

(x,0,z) = 2개 선택하는 경우

(0,0,z) = 1개 선택하는 경우

를 의미한다.

그럼 아래와 같은 식이 나온다.

    //하나만 선택
    if(biSearch(c,input)){
        write("1")
        close()
        return
    }
    for (i in input.indices) {
        //두 개 선택
        visited[i] = true
        if(biSearch(c-input[i],input)){
            write("1")
            close()
            return
        }
        //세 개 선택
        for (j in i + 1 until input.size) {
            visited[j] = true
            if(biSearch(c - (input[i] + input[j]),input)){
                write("1")
                close()
                return
            }
            visited[j] = false
        }
        visited[i] = false
    }

visited는 나머지 값을 이분 탐색할 때 x,y에서 선택한 값을 재사용하지 못하게 걸러주기 위함이다.

이분 탐색은 정렬된 리스트에서 가능함에 유의하자.

 

코드

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

lateinit var visited: BooleanArray

fun biSearch(search: Int, input: IntArray, ): Boolean {

    var s = 0
    var e = input.size - 1
    while (s <= e) {
        val mid = (s + e) / 2
        if (input[mid] > search) {
            e = mid - 1
        } else if (input[mid] < search) {
            s = mid + 1
        } else if(input[mid] == search){
            if(visited[mid]) e = mid - 1
            else return true
        }
    }
    return false
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n, c) = getIntList()
    val input = getIntList().toIntArray()
    visited = BooleanArray(n)
    //solve
    input.sort()
    //하나만 선택
    if(biSearch(c,input)){
        write("1")
        close()
        return
    }
    for (i in input.indices) {
        //두개 선택
        visited[i] = true
        if(biSearch(c-input[i],input)){
            write("1")
            close()
            return
        }
        //세개 선택
        for (j in i + 1 until input.size) {
            visited[j] = true
            if(biSearch(c - (input[i] + input[j]),input)){
                write("1")
                close()
                return
            }
            visited[j] = false
        }
        visited[i] = false
    }
    write("0")
    close()
}