[SW Expert Academy] 1289번 C++ 풀이

Sw Expert Academy 1289 - 원재의 메모리 복구하기 문제

SW Expert Academy

시간 제한	메모리 제한	난이도
(C++ 기준) TC 10개, 1초	힙, 정적 256MB, 스택 1MB	D3

 

문제 요약: 0으로만 이루어진 문자열에서, 입력받은 0과 1로만 이루어진 케이스로 바꾸는데 필요한 최소 변환 횟수를 구하라.

 

그리디 문제이다. 0으로만 이루어진 문자열에서 제일 왼쪽(인덱스 0)에서 시작하여 해당 위치가 입력받은 케이스의 위치와 다르면 정해진 방법으로 비트를 변환해주면 된다.

 

예시 케이스로 0111이라고 해보자. 제일 왼쪽, 그러니까 0번째 인덱스에서 시작해보자. 맨 처음은 0000일 것이다.

입력	0	1	1	1
현재	0	0	0	0

0번째 인덱스는 0이다. 이는 입력받은 케이스의 0번째 인덱스와 같기 때문에 패스한다.

입력	0	1	1	1
현재	0	0	0	0

첫번째 인덱스를 살펴보면 입력한 케이스와 다르기 때문에 변환한다.

입력	0	1	1	1
현재	0	0	0	0
변환	0	1	1	1

이후 입력한 값과 비교해보면 같기 때문에 답은 1이 된다.

 

다른 케이스인 1011로 보자.

입력	1	0	1	1
현재	0	0	0	0

0번째 인덱스를 비교하면 값이 다르기 때문에 비트 변환을 수행한다.

입력	1	0	1	1
현재	0	0	0	0
변환	1	1	1	1

입력한 값과 비교하면 아직 같지 않기에 계속해서 변환한다. 첫번째 인덱스를 보자. 역시 다르기 때문에 변환을 수행한다.

입력	1	0	1	1
현재	1	1	1	1
변환	1	0	0	0

역시 아직 같지 않기에 계속 변환하자. 두번째 인덱스도 다르기 때문에 또 변환한다.

입력	1	0	1	1
현재	1	0	0	0
변환	1	0	1	1

이후 값을 비교하면 같기 때문에 답은 3회가 된다.

 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

void bitChange(string& bin, int pos) {
    for (int i = pos; i < bin.length(); i++) {
        bin[i] = !(bin[i] - '0') + '0';
    }
}

int sol(string& bin) {
    string copyBin = "";
    int cnt = 0;
    
    for (int i = 0; i < bin.length(); i++) copyBin += "0";

    for (int i = 0; i < bin.length(); i++) {
        if (bin[i] != copyBin[i]) {
            bitChange(copyBin, i);
            cnt++;
            if (bin == copyBin) break;
        }
    }
    return cnt;
}

int main(int argc, char** argv) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int test_case;
    int T;
    string bin;

    cin >> T;

    for(test_case = 1; test_case <= T; ++test_case) {
        cin >> bin;
        cout << "#" << test_case << " " << sol(bin) << endl;
    }

    return 0;
}