[백준] 1439번 - 뒤집기

문제 >

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

 

입력 >

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력 >

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

 

해결방법 > 

같은 수가 나오는 구간을 하나의 덩어리로 생각했을 때, 적은 덩어리를 뒤집어주어야한다.

 

00011000은 000, 11, 000 세 구간으로 나눌 수 있다. 따라서 1이 나오는 구간을 뒤집으면 최소 횟수로 모든 숫자를 같게 만들 수 있다.

 

구간을 나누는 방법은 숫자가 바뀌는 순간을 카운트해준다.

첫 번째 문자와 숫자가 바뀌는 순간의 문자를 세주면 구간의 수를 구할 수 있다.

 

000 11 000 색이 칠해준 부분을 카운트 해주면

0으로 된 구간은 2, 1로 된 구간은 1개 이므로 1로 된 구간을 한 번 뒤집어 모두 같은 수로 만들어 줄 수 있다.

 

[C++]

#include <iostream>

using namespace std;

int main(){
    string s;
    int zero = 0, one = 0;

    cin >> s;

    if(s[0] == '0')
        zero++;
    else
        one++;

    for(int i = 1; i < s.size(); i++){
        if(s[i] != s[i-1]){
            if(s[i] == '0')
                zero++;
            else
                one++;
        }
    }
    cout << min(zero, one);
    return 0;
}

 

[JAVA]

package baekjoon;

import java.util.*;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String[] a = s.split("");
		int zero = 0, one = 0;
		
		if(a[0].equals("0"))
			zero++;
		else
			one++;
		
		for(int i = 1; i < a.length; i++) {
			if(!a[i-1].equals(a[i])) {
				if(a[i].equals("0"))
					zero++;
				else
					one++;
			}
		}
		System.out.println(Math.min(zero, one));	
	}
}

 

문제링크 >

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

1439번: 뒤집기