[Kotlin, B1] 백준 10275번 골드 러시

출처: unsplash.com

 

골드 러시(10275번)

Bronze 1

#수학 #구현

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

 

문제 내용

 

 

문제 접근

a, b 중에 하나를 2의 제곱수만을 이용해 만들어야 한다.

예를 들어 24는 16 + 8로 만들 수 있는데, 이때 차수가 가장 적은 수를 만들기 위해 2의 n제곱한 수에서 몇 번을 반으로 잘라야 만들 수 있는지 구하면 된다.

a, b에 정확히 요구된 수만큼만 들어가야 한다는 것과 a + b가 2의 n제곱과 같기 때문에 a와 b 중 하나만 구해도 나머지를 구할 수 있게 되기 때문에 이를 생각하게 되면 하나만 구해도 된다는 것을 알게 될 것이다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val t = bf.readLine().toInt()
    val answer = StringBuilder()

    for (i in 0 until t) {
        val (n, a, b) = bf.readLine().split(" ").map { it.toLong() }
        var gold: Long = 1
        for (j in 0 until n) {
            gold *= 2
        }

        if (a % 2 == 1L) {
            answer.append("$n\n")
            continue
        } else {
            var target = min(a, b)
            var cut = 0

            while (target != 0L) {
                if (gold > target) {
                    gold /= 2
                    cut++
                } else {
                    target -= gold
                }
            }

            answer.append("$cut\n")
        }
    }

    println(answer)
}

 

문제 풀이

a, b 중 더 작은 값을 구해서 사용하겠다.

n의 최댓값이 62이기 때문에 int 범위를 넘는다. 당연히 a, b도 int 범위를 넘을 수 있다.

long으로 값을 받아준다.

 

gold의 값은 pow 함수를 통해 구해줄 수는 있겠지만, 소수점 오차가 날 수도 있기 때문에 직접 반복해서 구해준다.

 

a, b가 홀수가 들어오게 된다면 1이 필요해지기 때문에 무조건 n번 잘라줘야 한다.

if로 걸러준 다음 짝수인 경우만 확인을 하면 된다.

 

target을 만들어서 a, b 중 더 작은 값으로 저장하고, 0이 될 때까지 잘라 주겠다.

target보다 gold가 더 크다면 gold를 정확히 반으로 나눠주고 cutting 카운트를 세준다.

target이 gold보다 더 큰 경우에는 target에서 gold를 빼준다.

 

 

문제 해결 과정

정확히 가방에 집어넣어야 한다는 사실을 모르고 문제를 보게 되면 이해하기가 힘들 수도 있다.

처음에는 case 10 1000 24를 보고 24보다 작은 제곱수가 16이기 때문에 10 - 4 = 6이라는 결론을 도출했는데 당연히 틀린 접근이다.

또한 홀수인 경우에는 무조건 1이 필요해지기 때문에 n번의 cutting이 필요해진다는 것을 알게 되면 시간을 절약할 수 있게 된다.