TIL Blog💻

[BOJ] 영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해!(20153)

  • Nov 25, 2020

[백준(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';
}
Search