[Kotlin, B1] 백준 32343번 드랍 더 비트

출처: unsplash.com

 

드랍 더 비트(32343번)

Bronze 1

#그리디 알고리즘 #브루트포스 알고리즘 #비트마스킹

2024 HICON 홍익대학교 프로그래밍 경진대회 B번

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

 

문제 내용

 

 

문제 접근

n자리의 2진수에서 각각 1의 개수가 a, b개인 2진수 2개가 주어질 때, 두 2진수의 xor 연산 결과가 제일 큰 경우를 구해야 한다.

n자리의 2진수에서 나올 수 있는 수는 2의 n승에 - 1만큼 나온다.

예를 들어 3자리의 2진수에서 나올 수 있는 최댓값은 2의 3승에 -1이므로 7이다. 1부터 7까지 나올 수 있다는 뜻이다.

 

그래서 1부터 n자리의 2진수에서 나올 수 있는 최댓값만큼 반복해서 반복되는 수를 2진수로 변환 후, 1의 개수를 확인해서 1의 개수가 a, b개인 case를 모두 구할 수 있다.

1의 개수가 a, b개인 case들을 모두 구하고 나면 a, b case들에서 aCase xor bCase가 가장 큰 값이 올 수 있는 경우를 찾아주면 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max
import kotlin.math.pow

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val size = readLine().toInt()
    val (a, b) = readLine().split(" ").map { it.toInt() }
    val aCases = mutableListOf<Int>()
    val bCases = mutableListOf<Int>()

    for (i in 0 until 2.0.pow(size).toInt()) {
        val value = i.toString(2)
        val oneCnt = value.filter { it == '1' }.length

        if (oneCnt == a) aCases.add(i)
        if (oneCnt == b) bCases.add(i)
    }

    var answer = 0
    for (i in 0 until aCases.size) {
        for (j in 0 until bCases.size) {
            answer = max(answer, aCases[i] xor bCases[j])
        }
    }

    println(answer)
}

 

문제 풀이

size자리의 2진수에서 나올 수 있는 모든 경우의 수를 for문으로 나타낸 후 반복한다.

i의 2진수값의 1의 개수가 a개면 aCase에 추가하고, b개면 bCase에 추가한다.

 

추가된 case들을 탐색해 모든 경우의 수를 모두 확인한다.

aCase xor bCase의 경우들 중 가장 큰 값을 출력한다.

 

 

문제 해결 과정

대회에서 풀 때는 a, b의 합이 n보다 크면 중복되는 수가 1개 이상 있다는 뜻이기 때문에 이를 이용해 문제를 해결하려고 시도했다.

3
2 2

위 case의 경우 a + b가 4이므로 각 자릿수에 중복되는 값이 최소 1개는 발생하기 때문에 2진수 111에서 1개의 0을 추가해서 낼 수 있는 가장 큰 값인 110 = 6을 이용해 문제를 풀이하려고 했는데 오답이 나왔다.

어떤 반례가 있는지는 모르겠다.

그래서 그냥 전체 탐색으로 해결했다.