문제 소개
이 문제에서는 이진 배열 bin[]과 두 값 L, R로 이루어진 Q개의 쿼리가 주어집니다. 우리의 목표는 C++로 이진 배열의 부분 배열(subarray)에 대한 10진수 값을 구하는 쿼리를 처리하는 프로그램을 작성하는 것입니다.
문제 설명 – 각 쿼리를 처리할 때마다 인덱스 L부터 R까지의 부분 배열, 즉 subarray[L...R]이 나타내는 이진수를 찾아 그 10진수 값을 출력해야 합니다.
예제로 이해하기
입력
bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0}
Q = 2
2 5
0 6출력
2 101
설명
쿼리 1의 경우 형성된 부분 배열은 {0, 0, 1, 0}입니다. 이는 이진수 0010에 해당하며, 10진수로 변환하면 2가 됩니다.
쿼리 2의 경우 형성된 부분 배열은 {1, 1, 0, 0, 1, 0, 1}입니다. 이는 이진수 1100101에 해당하며, 10진수로 변환하면 101이 됩니다.
해결 방법 1: 단순 순회 방식
가장 직관적인 해결 방법은 이진 배열을 인덱스 L부터 R까지 순회하면서 만들어지는 이진수를 구한 뒤, 이를 10진수 등가값으로 변환하는 것입니다.
구현 예제 프로그램
#include <iostream>
#include <math.h>
using namespace std;
int CalcDecimalValue(int bin[], int L, int R) {
int decimal = 0;
int j = 0;
for(int i = R; i >= L; i--){
decimal += bin[i] * pow(2, j);
j++;
}
return decimal;
}
int main() {
int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
int n = sizeof(bin) / sizeof(bin[0]);
int Q = 2;
int query[Q][2] = {{2, 5},{0, 6}};
for(int i = 0; i < Q; i++){
cout<<"For query "<<(i+1)<<": The decimal value of subarray is "<<CalcDecimalValue(bin, query[i] [0], query[i][1])<<"\n";
}
return 0;
}출력 결과
For query 1: The decimal value of subarray is 2 For query 2: The decimal value of subarray is 101
해결 방법 2: 사전 계산 배열 활용
또 다른 접근 방식은 사전 계산(pre-computed) 배열을 사용하는 것입니다. 각 인덱스 i부터 배열의 끝(n-1)까지의 비트로 만들어지는 10진수 값을 미리 저장해 두면, 쿼리를 처리할 때 L 위치의 값과 R+1 위치의 값 차이를 이용해 빠르게 답을 구할 수 있습니다.
배열의 i번째 값은 이진수를 10진수로 변환하는 공식을 오른쪽 끝, 즉 n-1부터 적용하여 다음과 같이 구합니다.
decimalArray[i] = bin[i]*2^(n-1-i) + bin[i+1]*2^(n-1-i+1) + … + bin[n-1]*2^(0)
동작 원리를 보여주는 예제 프로그램
#include <bits/stdc++.h>
using namespace std;
int decimalArray[1000];
void createDecimalArray(int bin[], int n){
memset(decimalArray, 0, n*sizeof(int));
decimalArray[n - 1] = bin[n - 1] * pow(2, 0);
for (int i = n - 2; i >= 0; i--)
decimalArray[i] = decimalArray[i + 1] + bin[i] * (pow(2,(n - 1 - i)));
}
int CalcDecimalValue(int L, int R, int n){
if (R != n - 1)
return (decimalArray[L] - decimalArray[R + 1]) / (pow(2, (n - 1 - R)));
return decimalArray[L] / (1 << (n - 1 - R));
}
int main(){
int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
int n = sizeof(bin) / sizeof(bin[0]);
createDecimalArray(bin, n);
int Q = 2;
int query[Q][2] = {{2, 5},{0, 6}};
for(int i = 0; i < Q; i++){
cout<<"For query "<<(i+1)<<": The decimal value of subarray is "<<CalcDecimalValue(query[i][0], query[i][1], n)<<"\n";
}
return 0;
}출력 결과
For query 1: The decimal value of subarray is 2 For query 2: The decimal value of subarray is 101