[백준/BOJ]12782. 비트 우정지수 [Silver 5]

12782. 비트 우정지수

문제출처 : https://www.acmicpc.net/problem/12782

code

#include <stdio.h>
#include <string.h>
#define ABS(a,b) (a>=b)? a-b:b-a
int main()
{
	char N[50][1000000], M[50][1000000];
	int T, similar_rate[50] = { 0 }, i, j, len = 0;
	int cnt_difference = 0, cnt_1 = 0, N_1cnt = 0, M_1cnt = 0;
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%s %s", &N, &M);
		len = strlen(N);
		for (j = 0; j < len; j++)
		{
			if (N[j] != M[j])
				cnt_difference++;
			if (N[j] == '1')
				N_1cnt++;
			if (M[j] == '1')
				M_1cnt++;
		}
		cnt_1 = ABS(N_1cnt, M_1cnt);
		similar_rate[i] = cnt_1 + ((cnt_difference - cnt_1) / 2);	
		cnt_difference = 0, N_1cnt = 0, M_1cnt = 0, cnt_1=0;
	}
	for (i = 0; i < T; i++)
		printf("%d\n", similar_rate[i]);
	return 0;
}

C언어로 작성했는데, 문제에 100만을 넘지않는다고 명시되어 있는데 C언어로는 문자열 길이 100만을 어떻게 할당해야할지 모르겠다. 동적할당 malloc도 써보고
N과M을 합쳐서 str[2][1000000] 으로도 할당해봤는데 segfault가 뜨는건 똑같다.
N[50][100]으로 하면 문제에서 나오는 예제 입력 출력은 제대로 나오는듯 하다.
결국 string범위의 문제인 것 같은데 이 문제를 C로 푸는사람은 나밖에 없고, 구글링해도 안나온다 ㅠㅠ 검색끝에 나와 똑같은 알고리즘으로 풀었는데 C++로 푼 사람이 있길래 그사람 코드를 넣었더니 되더라...

참고만 해보자

code(C++)

#include <iostream>
#include <string>
using namespace std;
int t, bitlength, dist, ab, bb;
string a, b;
int main() {
	ios::sync_with_stdio(false);
	cin >> t;
	while (t--) {
		dist = ab = bb = 0;
		cin >> a >> b;
		bitlength = a.length();
		for (int i = 0; i < bitlength; i++) {
			if (a[i] != b[i])
				dist++;
			if (a[i] - '0')	ab++;
			if (b[i] - '0')	bb++;
		}
		cout << (dist + abs(bb - ab)) / 2 << '\n';
	}
	return 0;
}

그리디하게 n번의 수행으로 풀 수 있다.
1. a와 b의 문자열을 입력받고, 각각에서의 1의 개수와 차이나는 비트의 수를 구해준다.
2. 최종 결과값은 (차이나는 비트수 + 두 개의 1의 비트 개수를 뺀 수) / 2 가 된다.

C언어의 한계인가 싶기도 하고 내가 부족한건가 싶기도 하다.
C++을 2학기때 배우긴 하지만, 미리 연습을 해놔야하나 싶기도 하다...

C++코드 출처 : https://m.blog.naver.com/khj94811/220994638870

8.10 수정

code

#include <stdio.h>
#include <string.h>
#define DIFF(a,b) (a>=b)? a-b:b-a
int main()
{
	char N[1000000] = { NULL };
	char M[1000000] = { NULL };
	int T, similar_rate = 0, i, j, len = 0;
	int cnt_difference = 0, cnt_1 = 0, N_1cnt = 0, M_1cnt = 0;
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%s %s", N, M);
		len = strlen(N);
		for (j = 0; j < len; j++)
		{
			if (N[j] != M[j])
				cnt_difference++;
			if (N[j] == '1')
				N_1cnt++;
			if (M[j] == '1')
				M_1cnt++;
		}
		cnt_1 = DIFF(N_1cnt, M_1cnt);
		similar_rate = cnt_1 + ((cnt_difference - cnt_1) / 2);
		printf("%d\n", similar_rate);
		cnt_difference = 0, N_1cnt = 0, M_1cnt = 0, cnt_1 = 0, similar_rate = 0;
	}
	return 0;
}

아는형의 도움을 받아 코드 다시짜보았다. 백준에서 통과는 되는데, 비주얼 스튜디오에서 실행하니까 터미널이켜지고 바로 종료가 되더라.... 그래서 그것만 해결하면 완벽할 것 같은데ㅠㅠ

여튼 알고리즘이 틀린건 아니니까 만족한다.