[Kotlin, S1] 백준 2205번 저울 추 만들기

출처: unsplash.com

 

저울 추 만들기(2205번)

Silver 1

#수학 #그리디 알고리즘

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

 

문제 내용

 

 

문제 접근

1부터 n까지의 무게를 가진 납과 주석을 합쳐서 2의 제곱수의 무게를 가지는 저울추를 만들어야 한다.

각 무게를 가지는 덩어리는 중복해서 사용이 불가능하다.

 

n이 1부터 5까지 이루어져 있을 때, n이 5일 때는 3을 대입해서 8을 만들 수 있다. 4일 때는 주석의 무게를 추가해서 (4, 4) 조합으로 8을 만들 수 있고 주석이 3일 때는 (3, 5)의 조합으로 저울추를 만들 수 있다.

정의된 무게를 만들기 위해 주석이 커지면 납이 작아지고, 납이 커지면 주석이 작아지는 특징을 이용해 중복을 허용하지 않고 주석의 무게를 구성할 수 있게 된다.

 

저울추의 무게는 현재 납의 개수에서 다음으로 큰 2의 제곱수로 정해줘야 한다.

n = 5일 때는 8, n = 9일 때는 16

 

정의된 저울추의 무게와 n을 통해 주석을 부여할 수 있는 납의 개수를 구할 수 있다.

저울추의 무게를 cw라고 할 때, cw - n을 하게 되면 cw - n부터 n번째 납까지 주석을 부여할 수 있다.

cw = 16, n = 9일 때, 7부터 9까지의 납에 주석을 부여할 수 있다.

(9, 7), (8, 8), (7, 9)

 

그러면 남은 납의 개수는 cw - n - 1이 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    var n = bf.readLine().toInt()
    val weight = Array(n + 1) { 0 }

    while (n > 0) {
        // 납의 개수를 이용해 만들 수 있는 저울추의 무게 구하기
        var cw = 1
        while (cw <= n) {
            // 현재 납의 개수보다 그 다음으로 큰 2의 제곱수를 구하기
            cw *= 2
        }

        // 나열 시작
        val start = cw - n  // 나열을 시작할 index
        for (i in start .. n) {
            // i번째 납에 해당하는 주석의 무게를 구하기 -> 중복되지 않게 주석의 무게를 정할 수 있음
            weight[i] = cw - i
        }

        // 남은 납의 개수를 정의
        n = start - 1
    }

    val answer = StringBuilder()
    for (i in 1 until weight.size) {
        answer.append("${weight[i]}\n")
    }

    println(answer)
}

 

문제 풀이

현재 n에 따라 cw를 정해준다.

cw는 n보다 큰 2의 제곱수들 중 가장 작은 2의 제곱수이다.

 

start로 나열을 시작할 납의 시작 지점을 정하고 n번 납까지 주석을 정의한다.

주석은 cw - i로 정할 수 있다.

 

마지막에 주석의 무게가 정해지지 않은 납의 개수를 구한다.

 

진행 프로세스(n = 10)

 

 

문제 해결 과정

저울추의 무게에서 납의 무게를 빼서 주석의 크기를 정해 중복을 없애는 것을 알아내는 것은 어렵지 않았는데,

얼마만큼의 납들에 주석을 채워야 하는지 알아내는 것이 어려웠다.

 

직접 답을 구해보면서 힌트를 얻을 수 있었다.