90. 백준 1439 번 C++ 코드 및 자세한 설명
안녕하세요 코딩하는 덕구입니다.
그리디 알고리즘 문제인 BOJ 1439 번 뒤집기 입니다.
https://www.acmicpc.net/problem/1439
1439번: 뒤집기
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모
www.acmicpc.net
백준 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++ 코드였습니다.
감사합니다.