[BOJ] 12782. 비트 우정지수

비트 우정지수 

클릭시 이동합니다!

어떻게 풀까?

할 수 있는 연산은 2개 입니다!

1. 두 수의 위치를 바꾼다.

2. 한 수의 비트를 바꾼다.

두 수의 위치를 바꿀 수 있다는 것은, 한 번의 연산으로 두 개의 수를 동시에 고칠 수 있다는 가능성을 가지고 있다는 것이죠.

한 번에 두 수의 비트를 옳게 바꾸는 방법은 무엇일까요!?

만약 바꾸고자 하는 두 수가 같다면, 연산의 의미가 없습니다.

만약, 바꾸고자 하는 두 수의 비트가 다르다고 하더라도, 이미 제대로 된 짝을 가지고 있다면, 바꾸는 의미가 없습니다.

즉, 한 번의 연산으로 두 개의 비트를 똑같게 만들고 싶다면, 위처럼 서로 짝이 맞지 않으면서, 서로 다른 비트를 가지는 두 비트의 자리를 바꿔야 합니다!

지금까지 한 번의 연산으로 서로 다른 두 자리에 있는 비트의 짝을 맞출 수 있는 것을 알아보았습니다!

그럼, 총 연산은 몇 번이 될까요?

비트가 0이고, 짝이 맞지 않는 자리가 5자리가 있다고 합시다!

그리고, 비트가 1이고, 짝이 맞지 않는 자리는 3개가 있습니다. 

결국, 한 번의 연산으로 두 자리의 비트를 맞출 수 있는 연산의 횟수는, 두 개의 수 중에 최솟값인 3번 입니다.

3번의 연산으로, 3개의 0과 1의 자리수 짝을 맞출 수 있습니다.

이렇게 자리를 맞추고 나면, 자리가 맞지 않은 0 비트 5자리 중 3 자리가 맞춰졌기 때문에, 이제 자리가 맞지 않는 비트의 수는 2개입니다.

해당 자리수들은 더이상 자리 바꾸기 연산으로 비트의 짝을 맞출수 없으므로, 비트를 반전 시켜서 짝을 맞춥니다.

즉, 3번 + 2번 = 5번 입니다.

그렇습니다! 결국 2개의 수 중에서 최댓값을 출력하면 되는 문제입니다!

코드

//https://www.acmicpc.net/problem/12782
//비트 우정 지수
 
#pragma once
#include<cstdio>
#include<cstring>
 
int n;
char str[2][1000001];
 
int BOJ12782() {
    scanf("%d\n", &n);
 
    while (n--) {
        scanf("%s %s\n", str[0], str[1]);
 
        int len = strlen(str[0]);
 
        int nums[256] = { 0 };
        for (int i = 0; i < len; i++) {
            if (str[0][i] != str[1][i]) {
                nums[str[0][i]] ++;
            }
        }
 
        printf("%d\n", nums['0'] < nums['1'] ? nums['1'] : nums['0']);
    }
    return 0;
}
 

여담

시간 복잡도는 두 문자열의 길이만큼 반복하는것 밖에 없기 때문에 O(N) 입니다.