C++ / 1439 / 뒤집기 ( 그리디 알고리즘 )

https://www.acmicpc.net/problem/1439

문제 요약

0과 1로만 이루어진 문자열 s가 있습니다. s에서 연속된 하나이상의 숫자를 잡고 모두 뒤집을 수 있습니다.

 

s = 0001100 일 때.

1. 전체를 뒤집으면 1110011이 됩니다.

2. 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번의 횟수로도 모두 같은 숫자를 만들 수있습니다.

 

s를 최소한으로 뒤집어서 같은 숫자로 만들 수 있는 횟수를 구해야합니다.

문제 풀이

1. 0을 뒤집는 경우와 1을 뒤집는 경우의 횟 수를 비교해야 하기 때문에 2번 반복문 돌립니다.

2. 문자열 길이 만큼 반복문을 돌려, 뒤집어야 하는 숫자가 나왔고, 그 숫자가 끝날때 ( 묶음 별로 세기 위함 ) 횟수를 증가시킵니다.

3. 이전 회차와 비교하여 더 작은 횟수를 저장하여 출력합니다.

주의할 점

횟수를 셀 때 더 작은 쪽으로 저장하게 해야 하고, 0또는 1을 전부 세는 것이 아닌 묶음 별로 세도록 조건을 주는것이 중요합니다.

코드

#include<iostream>

using namespace std;

string s;
int sum = 0, cnt = 0;

int main()
{
	cin >> s;
	//0을 뒤집는 경우와 1을 뒤집는 경우의 횟수를 봐야하기 때문에 2번 반복
	for (int i = 0; i < 2; i++)
	{
		// 횟수 체크 변수
		sum = cnt;
		cnt = 0;
		for (int j = 0; j < s.length(); j++)
		{
			if (s[j] != i+'0')
			{
				// 체크 하는 숫자가 끝날때 cnt 증가 
				if (s[j + 1] == NULL || s[j + 1] == i + '0')
				{
					cnt++;
				}
			}
		}
		// 0의 경우와 1의 경우 더 작은쪽 저장
		if (cnt <= sum)
		{
			sum = cnt;
		}
	}
	cout << sum;

	return 0;
}

반응형

예제1

0001100

결과1

예제2

11111

결과2

예제3

00000001

결과3

예제4

11001100110011000001

결과4

예제5

11101101

결과5