[C++] BOJ 12782 비트 우정지수

www.acmicpc.net/problem/12782

12782번: 비트 우정지수

코드

#include<iostream>
#include<algorithm>

using namespace std;
int t;
char num1[1000005], num2[1000005];
int main() {
	cin >> t;
	while (t--) {
		cin >> num1 >> num2;
		int change_one = 0, change_zero = 0;
		for (int i = 0; num1[i] != '\0'; i++) {
			if (num1[i] != num2[i]) {
				num1[i] == '0' ? change_zero++ : change_one++;
			}
		}
		cout << max(change_zero, change_one) << '\n';
	}
}

풀이방법

두 이진수를 비교해서 같은 위치에 서로 다른 값이 있는 자리만 남겨보자. 첫번째 이진수를 기준으로 했을 때, 0에서 1로 바뀌어야 하는 자리의 개수를 A, 1에서 0으로 바뀌어야 하는 자리의 개수를 B라고 하자. A가 B보다 크다고 가정하면, B번만큼 서로 자리를 교환해준 뒤 남은 (A-B)개의 자리의 숫자를 바꿔주면 된다. 따라서 최종 연산 횟수는 B+(A-B)회로, A와 같다. 이는 B가 A보다 클 때도 마찬가지로 성립한다. 따라서 결론적으로 A와 B 중 더 큰 값을 출력해주면 된다.

고민과정

이게 과연 그리디로 푼 것인지 모르겠다.