문제: BOJ 1094 — 막대기 English · 日本語
목표 길이는 1부터 64까지입니다. 처음 막대의 길이는 64이며, 막대를 절반씩 자르면 만들 수 있는 조각의 길이는 모두 64, 32, 16, 8, 4, 2, 1과 같은 2의 거듭제곱입니다.
목표 길이를 이진수로 나타내면, 켜진 비트에 해당하는 서로 다른 2의 거듭제곱의 합으로 표현됩니다. 선택된 각 조각 크기는 정확히 한 개씩 필요합니다. 예를 들어 23 = 16 + 4 + 2 + 1이므로 조각은 네 개 필요합니다. 따라서 답은 목표값의 켜진 비트 수입니다. Java의 Integer.bitCount를 사용하면 자르는 과정을 시뮬레이션하지 않고 바로 계산할 수 있습니다.
시간 복잡도는 O(1), 추가 공간 복잡도는 O(1)입니다.
Java
1
2
3
4
5
6
7
8
9
10
11
12
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
int target = Integer.parseInt(input.readLine());
System.out.println(Integer.bitCount(target));
}
}