백준 BOJ 1439 - 뒤집기

시험끝나고 알고리즘 재활을 시작하고 있는

코더빡입니다...

 

기말은 말아먹었지만 알고리즘까지 말아먹을순 없죠 ㅋㅋㄹㅃㅃ

실버로 감을 다시 잡아봅시다.

 

 

1439번 뒤집기는 이진수라는거에서 뇌절이 오면 안되는 문제였습니다.

이 문제의 핵심은

한번 뒤집을때 얼마나 효율적으로 뒤집을 수 있나 였습니다.

 

0에서 1로, 1에서 0으로 바뀌는 횟수를 세 줍니다

왜냐하면 뒤집는 구간을 제 맘대로 정할수 있기 때문에

1이 몇개있거나 0이 몇개있거나는

전혀 신경쓸 필요가 없기 때문입니다.

 

이제 다른 숫자가 등장한 횟수를 센 상태이고,

xxxYYxx에서 변화횟수는 2, 가장 효율적이게 xxxxxxx로 바꾼 뒤의 변화횟수는 0임에서 착안하면

한번의 Y*k 를 x*k 로 뒤집는 연산은 변화횟수를 2만큼 줄여낼 수 있게 됩니다.

이걸 계속 반복하면 모두 하나의 문자로 바꿀 수 있게 되는데,

뒤집기횟수는 단순히 변화횟수 / 2 를 통해 구해줄 수 있습니다.

구현하고 코너케이스 빼주면 AC.

 

#include <bits/stdc++.h>
using namespace std;

char arr[1234567] = {0};

int main(){
	scanf("%s", arr);
	int n = strlen(arr);
	
	int cnt = 0;
	for(int i=1; i<n; i++){
		if(arr[i] != arr[i-1]) cnt++;
	}
	printf("%d", (cnt+1)/2);
	return 0;
}

실버V 솔브속도는 얼추 안정됬네요

푸는거보다 블로그 글쓰는게 더 오래걸리는듯합니다 ㅎㅎ