오랜만!

BOJ 1439 - 뒤집기 링크
(2022.12.21 기준 S5)

문제

0과 1로 이루어진 문자열 S가 있고, 연속된 하나 이상의 숫자들을 모두 뒤집는 행동을 할 수 있다. 모두 같은 숫자로 만들기 위한 최소 행동 횟수 출력

알고리즘

간단한 그리디

풀이

모두 같은 숫자로 만들기 위해선 분명 0이나 1 하나만 모두 뒤집어야 최소 횟수가 되는 것은 자명하다.
그러면 이 문제에서 행동은 연속된 하나 이상의 모든 숫자들을 뒤집는 것이므로, 같은 숫자가 뭉쳐져 있는 것. 즉, 최대한 연속되는 것을 하나로 보고 가장 개수가 적은 것을 뒤집으면 되는 것이다.

예제 입력 4를 뭉쳐져 있는 것끼리 나누면 저렇게 된다.
그럼 당연히 1을 0으로 만드는 것보다 0을 1로 만드는 것이 최소 횟수가 된다.

코드

• Python

S = input().strip()

flip_zero = flip_one = 0 # 0과 1을 뒤집어야 하는 횟수
prev = S[0] # 직전 숫자

for i in range(1, len(S)):
    if prev != S[i]: # 현재 숫자가 직전 숫자와 다르면 연속된 동일된 숫자가 끝난 것이다.
        if prev == '0': # 직전 숫자의 뒤접어야 하는 횟수를 1 증가
            flip_zero += 1
        else:
            flip_one += 1
        prev = S[i]

# 끝 부분의 연속된 동일된 숫자는 아직 카운트되지 않았다.
if prev == '0':
    flip_zero += 1
else:
    flip_one += 1

# 뒤집는 횟수가 더 적은 것을 출력
print(min(flip_zero, flip_one))

• C++

#include <iostream>
#include <string>
using namespace std;
string S;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> S;
    int N = S.size();
    
    int flip_zero = 0, flip_one = 0; /* 0과 1을 뒤집어야 하는 횟수 */
    char prev = S[0]; /* 직전 숫자 */

    for (int i = 1; i < N; i++){
        if (prev != S[i]){ /* 현재 숫자가 직전 숫자와 다르면 연속된 동일된 숫자가 끝난 것이다. */
            if (prev == '0') flip_zero += 1; /* 직전 숫자의 뒤접어야 하는 횟수를 1 증가 */
            else flip_one += 1;
            prev = S[i];
        }
    }

    /* 끝 부분의 연속된 동일된 숫자는 아직 카운트되지 않았다. */
    if (prev == '0') flip_zero += 1;
    else flip_one += 1;

    /* 뒤집는 횟수가 더 적은 것을 출력 */
    cout << min(flip_zero, flip_one);
}

여담

요즘 새로운 알고리즘들을 공부한다고 블로그를 좀 잊고 있었다.
반평면 교집합, mo's, dinic, zkw mcmf, knuth 등등..
근데 모두 티어가 다 높거나 잘 알려지지 않은 (최소한 파이썬으론?) 알고리즘들이라서 아직 공개하고 싶지는 않다. ㅎ
내 보물 창고에 쏙

그리고 이제 c++로도 한번씩 올려볼 것이다.
최근에 추가 시간 없음이 달려 있는 문제에서, 완벽하게 같은 로직으로 python으론 TLE, c++로는 AC를 받아서 솔직히 많이 짜증났다. 대회에선 그렇다 하지만, 알고리즘 공부를 위해 만들어진 PS 사이트에서 굳이 대회와 같이 추가 시간 없음을 적용해야 하나..?
아무튼 C++로도 코드를 짜는 연습을 해야 함을 느꼈다.