Google online challenge 2020 for summer internships 2021

✔️ First Question: Size of the smallest subset with maximum Bitwise OR

Google Online Challenge 2020 - GeeksforGeeks

 

 

🎈 Question

양의 정수로 이루어진 배열이 있을 때,

비트 OR 연산의 합이 최대가 되는 부분집합 중에서 크기가 가장 작은 것을 찾는 문제이다.

해당 부분집합의 크기를 정답으로 출력하면 된다. 

Input, Ouput은 다음과 같다.

Input	Output
5 1 3 4 2	2

 

 

🎈 Solution

dp를 사용하면 짧고 간단하게 풀 수 있는 문제이다.

예시와 같이 [ 5, 1, 3, 4, 2 ]로 이루어진 배열이 주어진다면,

비트 OR 연산의 합이 최대가 되는 부분집합은 [ 5, 2 ], [ 5, 3 ], [ 4, 3 ] 이렇게 되고

가장 작은 집합의 크기는 2이므로 2를 출력하면 된다. 

 

1. 입력받은 배열을 내림차순으로 정렬(큰 수부터 더해야 합은 최대로 하면서 개수는 최소로 할 수 있기 때문)

 

2. for문을 돌면서 현재 arr 값과 OR 연산을 하는 것이 최적인지, 그렇지 않는 것이 최적인지 구한다.

예를 들어, 현재까지 비트 OR 연산 최댓값이 6(2진수: 110)이라면

1(2진수: 1)과 OR 연산을 했을 때는 7(2진수: 111)이 되지만,

2(2진수: 10)과 OR 연산을 하면 그대로 6(2진수: 110)이 되어 영향을 미치지 않으므로 이때는 OR 연산을 하지 않는 것이 최적이다.

연산 값이 증가할 때만 정답(cnt)을 1씩 증가시키면 된다.

 

3. 정답(cnt) 출력

 

 

💡 rbegin, rend

c++ vector에서 내림차순 정렬을 할 때 항상 추가 함수를 만들어서 sort의 마지막 인자로 넘겨주었는데,

sort(배열이름.rbegin(), 배열이름.rend()) 

이런식으로 하면 자동으로 내림차순 정렬이 된다!

 

 

💡 논리 OR(|) 연산과 비교 연산

OR 연산자와 비교 연산자를 사용할 때는

반드시 OR 연산식에 괄호를 사용하여 먼저 계산이 되도록 명시해야 한다.

if(dp[i-1] >= (dp[i-1] | arr[i]))

 

그렇지 않으면 컴파일시 에러 발생(vscode 기준)

 

 

🎈 Code(C++)

// Google online challenge 2020 for summer internships 2021
// https://www.geeksforgeeks.org/google-online-challenge-2020/
// First Question: Size of the smallest subset with maximum Bitwise OR
// dp

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
    int dp[5];
    int cnt = 1;
    vector<int> arr;
    arr.push_back(5);
    arr.push_back(1);
    arr.push_back(3);
    arr.push_back(4);
    arr.push_back(2);

    sort(arr.rbegin(), arr.rend()); // 내림차순 정렬

    dp[0] = arr[0];

    for(int i = 1 ; i < 5 ; i++) {
        if(dp[i-1] >= (dp[i-1] | arr[i])) {
            dp[i] = dp[i-1];
        }
        else {
            dp[i] = dp[i-1] | arr[i];
            cnt++;
        }
    }
    
    printf("%d\n", cnt);
    return 0;
}