(BOJ) 1094 막대기

1094 막대기

• 분류 : 수학, 비트마스킹

문제

지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다.

지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다.

막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.

• 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.
  • 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
  • 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
• 이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다.

X가 주어졌을 때, 위의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X가 주어진다. X는 64보다 작거나 같은 자연수이다.

출력

문제의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 출력한다.

예제 입력 1

23

예제 출력 1

4

예제 입력 2

32

예제 출력 2

1

예제 입력 3

64

예제 출력 3

1

예제 입력 4

48

예제 출력 4

2

Solution

Exapnder

import java.util.*

private var X: Int = 0 // 만드려는 막대의 길이

fun main() {
    input()
    solve()
}

private fun input() = with(Scanner(System.`in`)) {
    X = nextInt()
}

private fun solve() = println(Integer.toBinaryString(X).count { it == '1' })

Point of Thinking

• 최초에 주어지는 막대기의 길이가 64cm인 점, 절반으로 자르는 것을 반복하는 점에서 이진수를 greedy하게 배치하면 정답이 나옴을 유추할 수 있다.
• 다만 greedy하게 풀 필요도, 주어지는 모든 경우의 수를 메모이제이션할 필요없이 주어진 정수 N을 이진수로 바꾼 뒤 1의 개수만 출력하면 바로 Accepted.