baekjoon
백준 9527번 : 1의 개수 세기 [자바]
Meluu_
2025. 6. 5. 10:32
🧫 문제 분석
✔️ 출처
📖 문제
BigInteger 로 풀었는데 굳이 안써도 long타입으로 커버쳐지나보다.
2^i 인 수의 1의 개수를 누적합으로 구하는데 너무 큰 범위까지 구해서 그렇다.
10^16이하까지만 구하면됐는데 ...
포스팅한 이유는 사실 다른사람의 코드를 이해하기 위함이다.
https://tussle.tistory.com/1022
이 분의 풀이를 이해하고 정리해보겠다.
i = i번째 자리일때 최댓값까지의 1의 개수
i = 2 이면 000~ 111 까지의 1의 개수를 구하는 것이다.
i = 3 : 0000 ~ 1111까지의 1의 개수
2^n일때 1의 개수
dp[n] = dp[n-1] * 2 + 2^n if (n == 0) dp[0] = 1;이런 점화식이 나오는데
예를 들어 n = 3일때
우리는 0000 ~ 1111 까지의 1의 개수를 구해야한다.
dp[2] = 000~111까지의 1의 개수가 구해져있다.
그리고 1000 이후로부터도 1을 제외하고 생각하면 000~111까지의 개수이다.
따라서 dp[i-1] * 2 가 된다.
여기에 1000 ~ 1111까지의 개수는 2^3개이므로, 앞에서 1을 제외한 1의 개수를 더해준다.
dp[i-1] * 2 + 2^i
이제 이 누적합을 가지고 문제를 풀면된다.
110101 이 입력되었을때 길이는 6이다.
011111 일때 1의 개수는 알고 있다. dp[i-1]
100000 일때는 1의 개수는 1개이다. + 1
이제 나머지 를 구한다. 맨 앞 1을 제외한 나머지는 항상 맨 앞 1을 가지고 있기에
[010101] 개를 가진다.
100001
100010
100011
100100
100101
...
110101
그리고 맨 앞 1을 없애고 다음 차례로 넘어간다. 이를 반복한다.
10101 부터 다시 시작
🔅 문제 풀이 [ 내 풀이 ]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.math.BigInteger;
import java.util.*;
public class Main {
static BigInteger[] prefixOneCountSum;
static long[] powerOfTwo;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long n = Long.parseLong(st.nextToken());
long m = Long.parseLong(st.nextToken());
prefixOneCountSum = new BigInteger[64];
powerOfTwo = new long[63];
powerOfTwo[0] = 1;
for (int i = 1; i < powerOfTwo.length; i++) {
powerOfTwo[i] = powerOfTwo[i - 1] * 2;
}
precomputeOneCounts();
BigInteger countM = countOnesUpTo(m);
BigInteger countNMinus1 = countOnesUpTo(n - 1);
System.out.println(countM.subtract(countNMinus1));
}
private static BigInteger countOnesUpTo(long target) {
String binaryStr = Long.toBinaryString(target);
int length = binaryStr.length();
int prefixOneCount = 0;
BigInteger totalCount = BigInteger.ZERO;
for (int i = 0; i < length; i++) {
if (binaryStr.charAt(i) == '1') {
long partial = prefixOneCount * powerOfTwo[length - i - 1];
totalCount = totalCount
.add(BigInteger.valueOf(partial))
.add(prefixOneCountSum[length - i - 1]);
prefixOneCount++;
}
}
return totalCount;
}
private static void precomputeOneCounts() {
prefixOneCountSum[0] = BigInteger.ONE;
prefixOneCountSum[1] = BigInteger.valueOf(2);
for (int i = 2; i < prefixOneCountSum.length; i++) {
int pow = i;
int prefix = 0;
BigInteger sum = BigInteger.ZERO;
while (pow > 0) {
pow--;
sum = sum
.add(BigInteger.valueOf(prefix * powerOfTwo[pow]))
.add(prefixOneCountSum[pow]);
prefix++;
}
sum = sum.add(BigInteger.ONE);
prefixOneCountSum[i] = sum;
}
}
}(이전까지 앞에 나온 1의 개수 * 해당 자리에서 1이 나올 수 있는 횟수) + 이전 자리 누적합
이 풀이의 경우
2^i 를 기준으로 누적합을 진행하였다.
2^0 = 1
2^1 = 2
2^2 = 5
2^3 = 13 1000 까지
다른사람 풀이의 경우
i = 2이면 111
i= 3 이면 1111 까지
🔅 문제 풀이 [ 다른 사람 풀이 ]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
public class Main {
static long[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long n = Long.parseLong(st.nextToken());
long m = Long.parseLong(st.nextToken());
dp = new long[55];
// idx : idx자리의 위치가 최댓값일때 1로 꽉채울 경우 1의 개수 ex) idx = 3 -> 111 , idx = 0 -> 1, idx = 1 -> 11 까지 채우는 개수
dp[0] = 1;
for (int i = 1; i < dp.length; i++) {
dp[i] = (dp[i - 1] << 1) + (1L << i); // dp[i] = dp[i-1] * 2 + 2^i
// 왜 2^i냐면 앞에 새로운 1이 붙는데 기존 dp[i-1] 의 개수만큼 더 추가되면서 1이 하나씩 더 붙기때문
// ex ) i = 2 -> 0~7
// 전반 dp[i-1] 000, 001, 010, 011
// 후반 dp[i-1] 100, 101, 110, 111
// 총 4개의 수 즉 ,i^2개가 추가됨
// dp[n-1] ~ dp[n]-1 까지는 n개의 추가 비트가 필요
// 이유는 idx의 규칙때문, idx = 2일때는 7까지이므로 사실상 앞 idx의 1의 개수 -1 개까지를 구하기때문에 2^idx만큼 추가될 수 밖에 없음
}
long answer = calc(m) - calc(n - 1);
System.out.println(answer);
}
// 1010101 일때
// 1000000 까지 목표로 1의 개수를 구함
// 0111111 개수 (dp[i-1]) +
// 1000000 일때 1의 개수 (1개)
// 1010101 - 100000000 일때 나머지
// 0010101 은 앞 1이 고정이므로 생길때마다 1이 추가되었을 것임
//따라서 n - 1L<<1 개
private static long calc(long n) {
long cnt = n & 1; // 첫째 자리
int size = (int) (Math.log(n) / Math.log(2)); // 자릿수 구하기
for (int i = size; i > 0; i--) {
if ((n & 1L<<i) == 0) continue;
cnt += dp[i - 1] + (n - (1L << i) + 1); // i번째 1까지 구하는게 dp[i-1] + i번째 1일때 1000.. 일때 1가지 + i번째 자리를 가질때 N - 1L<<1 의 수까지는 다 1을 고정적으로 가짐
n -= (1L << i);
}
return cnt;
}
}