백준 1439번 : 뒤집기
1450번: 냅색문제
첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다.
www.acmicpc.net
/* 문제 설명 */
0과 1로 이루어진 문자열이 있을 때, 0 → 1, 1 → 0으로 뒤집을 수 있다.
이 때, 문자열의 모든 숫자가 같도록 만드려면 최소 몇 번을 뒤집어야할까?
S = 0001100
0000000 : 1을 뒤집는 경우 1번만에 같은 숫자로 만들 수 있다.
1111111 : 0을 뒤집는 경우 2번만에 같은 숫자로 만들 수 있다.
따라서 최소로 뒤집는 경우는 1이다.
/* 해결 방안 */
1) 가장 쉽게 떠오르는 풀이는 0의 집합의 개수와 1의 집합의 개수를 세어주고, 둘 중 적은 수를 고르는 풀이다.
S = 0001100
0의 집합의 개수 : 2
1의 집합의 개수 : 1
조금 더 간단한 풀이를 떠올려보자!
2) 또 다른 풀이로는 '어차피 둘 다 같다'라는 사실에 집중하면 떠올릴 수 있다.
이게 무슨 소리냐면, 일단 문자열을 그림으로 표현해봤다.
네모는 한 숫자의 집합이라는 뜻이다.
110001이 있다면, 우리는 이걸 101로 변환한다음에 개수를 세어주려고 한다.
근데 110001 이든 001110 이든, 결국 ■□■ 이런 모양이 된다.
따라서 '0에서 1로 바뀌는지, 1에서 0으로 바뀌는지' 따질 필요 없이, 지금 보고 있는 숫자와 다음 숫자가 다른지만 확인해주면 된다.
그리디적으로 접근하면, 결국 가장 적은 네모를 뒤집어줘야하므로, 위의 그림에서 흰 색 박스를 뒤집어 주면 된다.
따라서 우리는 흰 색 박스의 개수만 세어주면 되는데, 이는 전체 네모의 개수 / 2 라는 것을 알 수 있다.
그렇다면, 전체 네모의 개수는 어떻게 구할 수 있을까?
for문을 돌면서 arr[i] != arr[i+1]인 경우의 수를 세어준다음에 +1 을 해주면 된다.
아래 그림을 보면 쉽게 이해할 수 있다.
3번 다르다는 것은 총 4개의 박스가 있다고 해석되기 때문이다.
물론 빨간색의 개수를 세어줘도 문제를 풀 수 있지만, 이 경우에는 홀수/짝수에 대한 분기처리가 필요하다.
/* 구현 과정 */
1. for문을 돌면서, arr[i] != arr[i+1]인 경우의 수를 세어준다.
2. 위에서 구한 결과에 +1을 한 후, /2를 해준다.
/* 소스 코드 */
#include <bits/stdc++.h>
using namespace std;
int ans = 1;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
string s; cin >> s;
for (int i = 0; i + 1 < s.size(); i++)
if (s[i] != s[i + 1]) ans++;
cout << ans / 2;
}
위의 코드에서는 +1을 해주는 대신 ans를 초기화하는 과정에서 아예 1을 넣어주고 시작했다.
/* 얻어갈 점 */
1. 조금 더 나은 풀이가 있는지 확인하면서 풀자!