90. 백준 1439 번 C++ 코드 및 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그리디 알고리즘 문제인 BOJ 1439 번 뒤집기 입니다.

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

1439번: 뒤집기

 

 

백준 1439 번 C++ 정답 코드입니다. 설명은 아래에 있습니다.

char = input()

cnt = 1
for i in range(len(char) - 1):
    if char[i] != char[i+1]:
        cnt += 1

print(cnt//2)

 

문제 요약

문제에는 0과 1로 이루어진 숫자가 주어집니다.

연속된 하나 이상의 숫자를 잡고 모두 뒤집을 수 있을 때

최소한의 행동으로 모든 숫자를 같게 하는 횟수를 구하는 문제입니다.

 

문제 접근

0과 1로 이루어진 숫자는

둘 중 적게 나온 연속된 같은 종류의 숫자 만큼 뒤집으면 최소한의 행동으로 모두 같은 숫자로 만들 수 있습니다.

 

1. 숫자가 들어오면 앞서 들어온 숫자와 다른지 같은지 체크합니다.

2. 다르다면 숫자를 셉니다.

3. 모든 숫자를 체크하고 난 후 2로 나눈 후 나머지를 버립니다.

예를들어 9번 달라지면 연속된 0또는 1이 5번, 4번 나오게 되는데

이때 적은 수만큼 뒤집으면 최소한의 행동으로 모든 숫자를 같게 만들 수 있기 때문입니다. 

 

C++ 코드 구현

0과 1로 이루어진 숫자를 입력받습니다.

cin >> S;

 

cnt를 1로 초기화 하고

앞의 숫자와 뒤의 숫자가 다르면 cnt를 1늘려주고

int cnt = 1;
for (int i = 0; i < S.length() - 1; i++) if (S[i] != S[i + 1]) cnt++;

 

2로 나눠 나머지를 버리고 출력합니다.

cout << cnt/2;

 

백준 1439 번 뒤집기 C++ 최종 코드입니다.

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

int main(){
    cin >> S;

    int cnt = 1;
    for (int i = 0; i < S.length() - 1; i++) if (S[i] != S[i + 1]) cnt++;

    cout << cnt/2;
    return 0;
}

 

백준 1439 번 뒤집기 자세한 설명 및 C++ 코드였습니다.

감사합니다.