[백준(BOJ)] 20153_영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해! C++
문제 : BOJ_20153번 영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해!
문제 설명
우선 n 개의 자연수가 주어집니다.
이 n 개의 수를 모두 이진수로 바꾸고 각 자리의 1의 개수를 조회합니다.
각 자리수의 1의 개수가 홀수이면 최종 결괏값에 (2^자리수)를 더해주고, 짝수이면 더하지 않습니다.
이때 최종 결괏값이 최대가 될 수 있도록 n 개의 자연수 중 최대 하나의 자연수를 제외할 수 있습니다.
마지막으로 결괏값을 띄어쓰기 없이 두 번 출력하면 정답입니다.
Solution
완전 탐색, 수학
주어질 수 있는 수의 최고값이 2222222이므로, 그에 맞게 2222222의 숫자에 이진수로 바꿨을 때의 자릿수를 이차원 배열로 선언해 줍니다.
그런 다음 각 자연수를 이진수로 바꾸고 앞서 만든 배열에 자리수의 정보를 넣어 줍니다.
그 뒤에 n 개의 모든 자연수의 각 이진수 자리수를 기준으로 계산한 최댓값을 구한 뒤, n 번 순회하며 각 자연수를 제외했을 때의 값들과 최댓값을 비교합니다.
이렇게 완전 탐색으로 나온 최댓값이 정답이 됩니다.
시간 복잡도가 까다로운 문제이므로, 줄일 수 있는 연산들은 최대한 줄여야 합니다.
Description
- pow 함수의 사용을 줄이기 위해 처음에 배열에 pow 함수의 값을 모두 할당했습니다.
#include <iostream>
#include <algorithm>
#include <stack>
#include <cmath>
using namespace std;
int value[23];
int numValue[2222223][23];
int powArr[23];
int main(){
for(int i=0;i<23;i++) powArr[i] = pow(2,i);
int n;
cin >> n;
for(int i=0;i<n;i++){
int num;
cin >> num;
stack<int> s;
int cnt = 0;
while(num){
if(num%2){
numValue[i][cnt]=1;
value[cnt] += 1;
}
num/=2;
cnt++;
}
}
for(int i=0;i<22;i++){
value[i]%=2;
}
int result = 0;
for(int i=22;i>=0;i--){
if(value[i]) result+=powArr[i];
}
int final=result;
for(int i=0;i<n;i++){
int nowResult = result;
for(int j=0;j<22;j++){
if(numValue[i][j]==0) continue;
if(value[j]) nowResult -= powArr[j];
else nowResult += powArr[j];
}
final= max(final,nowResult);
}
cout <<final<< final << '\n';
}
PREVIOUS[Spring] 서버 실행 시 DB Table 생성