SWEA - 1289 원재의 메모리 복구하기

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV19AcoKI9sCFAZN

SW Expert Academy

모든 bit가 0인 초기화 상태에서 입력값으로 주어진 상태로 만들기 위해 고쳐야 하는 최소 횟수를 구하는 문제였다.

 

문제 풀이

단순히 0의 값과 1의 값을 구해 더 적은 횟수가 정답인 줄 알았는데, 현재 bit를 변경하면 현재 위치부터 맨 끝까지 해당 bit로 덮어씌워지는 문제였다.

 

현재 값을 초기 상태인 0으로 지정하고, 메모리 bit의 맨 앞부터 순회하면서 다른 수가 나오면 다음 수로 변경했다. 그리고 이렇게 변경한 횟수가 최소 횟수로 정답이 된다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin>>T;
	
	for(test_case = 1; test_case <= T; ++test_case)
	{
        string str;
        cin >> str;

        //앞에서부터 바꿔 나가야함
        int nowNum = 0;
        int cnt = 0;
        for(int i=0;i<str.size();i++){
            if(str[i]-'0' != nowNum){ //뒤에 싹 바꿔줘야함
                nowNum++;
                nowNum %= 2;
                cnt++;
            }
        }
        
        printf("#%d %d\n",test_case, cnt);
	}
	return 0;
}