問題: BOJ 1094 — 棒 English · 한국어
目標の長さは1から64です。最初の棒の長さは64で、棒を半分ずつ切ると作れる棒の長さは64、32、16、8、4、2、1のような2のべき乗になります。
目標の長さを2進数で表すと、立っているビットに対応する異なる2のべき乗の和になります。選んだ各サイズの棒はそれぞれ1本ずつ必要です。例えば23 = 16 + 4 + 2 + 1なので、棒は4本必要です。したがって、答えは目標値の立っているビット数です。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));
}
}