글을 적기에 앞서, 필자의 방법은 효율적인 점화식 도출에 처참하게 실패하고 보편적인 풀이에 비해 코드가 매우 길어지고 지저분해졌음을 알립니다. 찾고 찾다 도저히 다른 풀이가 이해되지 않아 꼼수를 원하신다면 읽으셔도 좋습니다.
그땐 뭘 몰랐지
오랜만에 재밌는 문제라고 생각했다. solved.ac의 class별 풀이를 따라가다 보면 class3에선 bfs/dfs를, class 4에선 다익스트라를, class5(현재 진행중)에선 최소 신장 트리를 활용하는 문제를 자주 만나게 되는데, 이번 문제는 알려진 알고리즘을 공부해서 활용하는 게 아니라 혼자 풀이를 생각해 볼 법해 보였기 때문이다. 더불어 존재만 알고 사용해본 적은 없는 비트연산자를 사용할 법한 문제였기 때문에 문제를 읽을 때 부터 신이 났다. 나도 이제 간지나게 << 같은 걸 쓸 수 있겠구나. ^를 사용한 연산을 해보겠구나! 2진수 다뒤졌다😎😎😎 라고 생각했다. 잘못된 생각이었다.
일단 접근법을 고민해봤다
일단 입력 범위가 너무 큰 문제다보니 범위 내의 숫자를 모두 이진수로 변환해서 1의 숫자를 세는 방법은 사용할 수 없었다. Gold2 문제가 그렇게 단순한 풀이를 요구할리도 없었다. 직관적으로 2진수는 01의 반복이기 때문에 순차적으로 진행될 경우 일련의 규칙이 있을게 분명해보였고, 하나씩 찾아보기로 했다. 일단 2진수를 순서대로 적어봤다.
1
10 11
100 101 110 111
1000 1001 1010 1011 1100 1101 1110 1111
10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111
각 자리수가 증가할 때마다 앞에 1이 추가되어 있을 뿐이지 아랫자리수의 패턴이 반복된다. 당연하게도 1이 등장하는 패턴도 반복된다.
1자리 수 : 1 -> 1개
2자리 수 : 10 11 -> 1개 2개
3자리 수 : 100 101 110 111 -> 1개 2개 2개 3개
4자리 수 : 1000 1001 1010 1011 1100 1101 1110 1111 -> 1개 2개 2개 3개 2개 3개 3개 4개
단순 자리수만 하나 늘어난 형태이기 때문에 n번째 자리수는 n-1번째 패턴을 한 번 반복하고, n-1번째의 각 1의 개수에 +1 한 형태로 한 번 더 반복된다. 위의 규칙을 통해 5자리 1의 개수를 예상해보면 아래와 같을 것이다.
1개 2개 2개 3개 2개 3개 3개 4개 2개 3개 3개 4개 3개 4개 4개 5개
개슈탈트붕개
하나의 규칙을 알았으니 이제 활용법을 고민할 단계다. 입력의 범위가 10^16까지이기 때문에 쌩으로 배열을 만들어 욱여 넣을 수는 없다. 필자는 여기서 시간이 꽤 오래 걸렸다. 배열을 2차원으로 나눠도 숫자는 터무니없이 많고, 어찌저찌 그걸 해결한다고 해도 outOfMemory든 뭐든 튀어나올 게 분명했기 때문이다. 한참을 고민하다 선택한 방법은 자리수별 1의 개수 합이었다. 2진수 자리수별로 1이 등장하는 개수를 더해서 처리한다면 뭔가 실마리가 잡힐 것 같았다.
1
3 2+1
8 3x2+2
20 8x2+4
48 20x2+8
.
.
.
digit[n] = digit[n-1] x 2 + 2^(n-1)
이렇게 하면 2진수 n자리에서 등장하는 모든 1의 개수를 구할 수 있다. 이 문제는 두 숫자 A,B사이에 등장하는 모든 경우를 더해야하므로, 누적합을 통해 1~n자리까지의 1을 숫자를 처리할 수 있도록 코드를 구성했다. 각 자리수까지 등장하는 1의 개수를 세었으니, 이제는 특정 숫자까지 등장하는 1의 개수를 계산할 차례다. 아래 두개의 콜아웃은 문제를 풀며 파일 하단에 적은 주석을 그대로 가져왔다.
순서 1. 10진수 A를 2진수로 변환한다. Long.toBinaryString(A) ex ) 28 -> 11100 2. 5자리(11111)까지의 누적합은 80... 0인 부분에 해당하는 누적합을 제거해준다 3. 80 - (4+4+5) [ 11101, 11110, 11111 ] -> 답은 67 ㄴ 111 은 앞에 있고 뒤의 00 두자리만 바뀌므로 각 자릿수 digit[0] = 1, digit[1-1] = 1, digit[1-2] = 2 에 각 앞에 등장한 1의 개수인 3씩더해서 4,4,5를 빼게 된다. ㄴ 즉 바꿔보면 80-(1+1+2)-(3*3) 그러나 해당 자릿수를 어떻게 계산하느냐? ㄴ 2^2 아래의 자연수 1,2,3 ㄴ 2^n - 1 을 하면 1의 개수에 곱할 숫자가 나온다 ㄴ 자리수까지의 누적합 - (0인 자리수의 누적합 ) + (1인 자리수의 누적합)
위에 적은 바를 토대로 26에 대한 계산을 한 번 더해보면
ex2 ) 26 -> 11010 80 - 3자리 + 2자리 - 1자리 80 - ( (2^3-1)*2 + 12 ) + ( (2^2-1)*2 + 4 ) - ( 1 + 3(1의자리 앞에서의 1의 개수는 3개다) ) 80 - 26 + 10 - 4 answer = 60 반대로 해보자. 4자리 수까지인 20에서 더하기 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 16 17 18 19 20 21 22 23 24 25 26 1 2 2 3 2 3 3 4 2 3 3 28 32 + 28...? = 60 결국 방법 자체는 해결... 그러나, 하지만, but, however, nevertheless... 지저분하다. 맘에 안든다!
문제 해결에 필요한 단서는 모두 찾은 것 같다. 위를 토대로 코드만 작성하면 되는데, 위의 2^n-1 을 구현하는 과정에서 Math.pow를 사용한다면 약간의 오차가 발생한다. 부동소수점을 사용하지 않도록 간단한 pow 메서드를 직접 구현해서 사용해야 입력 데이터가 크더라도 오차가 발생하지 않는다. 아래는 정답 코드.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
// 자리수 별 1의 개수
// 10^16을 2진수로 변환하면 54자리 수가 나오므로 배열의 길이는 55까지 지정해준다.
static long[] digitCount = new long[55];
// 각 자리까지의 1의 개수 누적합 배열
static long[] prefixSum = new long[55];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 1자리수는 1로 시작한다.
digitCount[0] = 1;
prefixSum[0] = 1;
// 입력 받고
long A = Long.parseLong(st.nextToken());
long B = Long.parseLong(st.nextToken());
// 배열 값 계산
for(int i = 1 ; i<55; i++){
digitCount[i] = (long) (digitCount[i-1]*2 + pow(2, i-1));
prefixSum[i] = prefixSum[i-1] + digitCount[i];
}
// 각 숫자까지 등장하는 1의 개수를 계산한다.
// 범위가 A를 포함하므로, A-1까지 계산한 뒤 차감
long a = getCount(Long.toBinaryString(A-1));
long b = getCount(Long.toBinaryString(B));
// A가 1인 경우 1자리수 를 포함하여 계산하므로, 차감할 숫자는 0이 된다.
if(A==1){
a = 0;
}
// 출력
System.out.println( b - a );
}
// 주어진 2진수까지 등장하는 1의 개수를 계산하는 메서드
public static long getCount(String binary){
// 리턴 변수 선언
long ret = 0L;
// 자리수마다 등장한 1의 개수를 저장할 변수
// 0보다 큰 이진수는 첫자리가 반드시 1이므로 1로 시작
long oneCount = 1;
// 0과 1의 변화를 판단할 변수
boolean check = false;
// 시작하는 자리수까지 등장하는 1의 개수를 더해서 시작한다.
// 0이 등장할 때마다 차감, 1이 다시 등장한다면 필요한 값을 더해줄 것이다.
ret += prefixSum[binary.length() -1];
for(int i = 1; i<binary.length(); i++){
// 자리수를 판단할 변수
// 배열에선 오른쪽으로, 우리가 적는 숫자에선 왼쪽으로 자리수가 증가한다
// 따라서 뒤집어서 시작
int digit = binary.length() - i -1;
if(binary.charAt(i)=='1'){ // 현재 자리의 숫자가 1이면
// 누적합에서 시작했으므로 0이 등장하기 전까진 숫자를 더할 필요가 없다.
// 만약 0이 등장해서 check가 true 로 바뀌면 해당 자리수까지의 누적합을 더해준다.
if(check){
ret += prefixSum[digit];
ret += (pow( 2, digit+1 )-1) * oneCount;
check=false;
}
// 등장한 1의 개수를 추가해준다.
oneCount++;
}else{ // 0이면
if(!check){
check = true;
ret -= (pow( 2, digit+1 )-1) * oneCount;
ret -= prefixSum[digit];
}
}
}
return ret;
}
// Math.pow는 double타입을 반환하므로 숫자가 커질 때 약간의 오차가 발생한다.
// 간단하게 제곱 함수를 구현해준다.
public static long pow(int a, int b){
if(b==0){
return 1L;
}
long ret = 1L;
for(int i = 0 ; i<b; i++){
ret *= a;
}
return ret;
}
}
통과는 했지만
풀면서 정말 자괴감을 많이 느꼈던 문제였다. getCount 함수 안의 check 변수라거나 prefix와 digitCount 배열을 따로 사용한 점 등 당장 어떻게 고치겠다 생각은 나지 않지만 분명 구현을 위해 주먹구구식으로 처리한 곳들이 존재하고, 점화식 또한 아무리 봐도 훨씬 간결하게 만들 수 있어보여서다. 다른 분들의 풀이를 보면 내 코드만큼 길지도 않을 뿐더러 시프트 연산을 통해 훨씬 간결하게 처리한 부분도 보였다. 결국 나도 비트연산 고수가 되겠다는 다짐은 접은 채로 통과에 급급해 요상한 코드가 나왔는데, 스스로의 코딩 스타일과 성향에 대해 돌아보게 되는 계기가 되었다. 2진수 다뒤졌다는 무슨... 조져진건 나였고..🥲
테스트 케이스 참고
https://gooddaytocode.blogspot.com/2017/02/latin-america-regional-contests.html
큰 수에 대한 입출력 예시를 찾을 수 있다. 필자는 Math.pow의 오차를 예상만 하던 상태에서, 위 링크의 입출력 데이터를 통해 정확하게 확인할 수 있었다.
내가 사용했던 케이스는 2번 케이스인
Input
1000000000000000 10000000000000000
Output
239502115812196372
Math.pow에선 마지막 4자리에서 오차가 발생했고, pow메서드를 직접 구현해 사용하자 다른 코드의 수정 없이 통과됐다. 부동소수점 이거 무서운 놈이다.
