[SWEA][C++] 1289. 원재의 메모리 복구하기

문제

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

SW Expert Academy

 

문제 이해

• 초기화 상태(모든 bit가 0)에서 원래 상태로 복구해야 한다.
• 복구할 때는 bit 중 하나를 골라 0 또는 1을 결정하고, 해당 값이 메모리의 끝까지 덮어씌워진다.
• 초기화 상태에서 원래 상태로 복구할 때 최소 수정 횟수를 구한다.

 

입출력 예시

1. 입력: 0011
   0000에서 3번째 bit를 골라 1로 설정하면 0011이 되므로, 출력값은 1이다.
2. 입력: 100
   000 → 111 → 100로, 출력값은 2이다.

 

문제 풀이

🔍 접근

반복문을 이용해서 초기화 상태와 원래 상태 메모리를 첫 번째 bit부터 하나씩 비교하면 해결할 수 있다.

그런데, 이 방법대로면 초기화 상태 변수를 만들어서 원래 상태의 bit 길이만큼 0을 할당해야한다.

메모리 길이가 50일 경우, 50번 0을 추가해야하는 일이 발생한다.

이 과정을 생략하는 방법에 대해 생각해보자.

 

🔨 구현

초기화 상태와 원래 상태 메모리를 더 효율적으로 비교할 수 있는 방식을 떠올릴 수 있다.

bit를 한 번 수정할 때는 해당 bit부터 끝까지 수정되므로,
초기화 상태의 현재 bit를 나타내는 임시 변수를 생성해 0, 1로 바꾸면서 원래 상태 메모리와 비교할 수 있다.

1. 임시 변수(temp)의 초기 상태는 '0'이다.
2. 원래 상태 string을 순회하는 반복문을 실행한다.
    - 원래 상태의 현재 bit가 temp와 같으면, 다음 bit로 이동한다.
    - 다르면, temp를 변경하고(0 → 1, 1 → 0) 변경 횟수를 늘린다.

 

코드

#include<iostream>

using namespace std;

int main() {
    int T;

    cin >> T;

    for (int test_case = 1; test_case <= T; ++test_case) {
        string origin;
        int ans = 0;
        char temp = '0';

        cin >> origin;

        for (char c: origin) {
            if (c == temp) continue;

            temp = c;
            ans++;
        }

        cout << '#' << test_case << ' ' << ans << '\n';
    }

    return 0;
}