[1439번] 뒤집기

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

 

그리디 알고리즘을 공부하기 위해 다음 문제를 풀었다.

그리디 선택: "어떤 목표를 고를 것인가?"

이 문제의 최종 목표는 두 가지뿐이다.

• 목표 A: 문자열 전체를 0으로 만들기
• 목표 B: 문자열 전체를 1으로 만들기

이때의 그리디한 선택은 둘 중 어떤 목표를 고르는 것이 더 이득(최소 횟수)인가?를 결정하는 것이다.

---

각 목표의 비용 계산하기

이제 각 목표를 달성하는 데 필요한 '비용(뒤집는 횟수)'을 계산해야 합니다.

1. '목표 A' (모두 0)를 선택한 경우

• 비용: '1'로 된 덩어리(그룹)의 개수
• 이유: 001101110 같은 문자열이 있다고 해봅시다. '1' 덩어리는 11과 111로 총 2개이다.
• '1' 덩어리를 없애려면 그 덩어리를 뒤집어야 합니다. 11을 뒤집고(1번), 111을 뒤집으면(2번) 모두 '0'이 된다.
• 핵심은 서로 떨어져 있는 '1' 덩어리들은 한 번의 뒤집기로 동시에 없앨 수 없다는 것입니다. 따라서 '1' 덩어리의 개수만큼의 횟수가 '최소' 횟수가 된다.

2. '목 ' (모두 1)를 선택한 경우

• 비용: '0'으로 된 덩어리(그룹)의 개수
• 이유: 위와 동일합니다. 001101110에서 '0' 덩어리는 00, 0, 0으로 총 3개이다.
• 모두 '1'로 만들려면 '0' 덩어리들을 뒤집어야 하며, 최소 3번이 필요하다.

---

결정

이제 우리는 두 가지 선택지의 비용을 모두 알게 되었다.

• '목표 A' (모두 0)로 가는 비용: 1 덩어리 개수 (2개)
• '목표 B' (모두 1)로 가는 비용: 0 덩어리 개수 (3개)

그리디 알고리즘은 이 두 가지 선택지 중 "지금 당장 가장 비용이 적게 드는(최적인) 선택"을 하면 된다.

"2번 뒤집는 것과 3번 뒤집는 것 중 당연히 2번 뒤집는 것이 이득이네! 나는 '모두 0'으로 만드는 목표를 선택하겠다!"

 

다음전략을 코드로 작성하면

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String str = sc.nextLine();

        if (str.length() <= 1) {
            System.out.println(0);
            return;
        }

        int group0 = 0;
        int group1 = 0;

        if (str.charAt(0) == '0') {
            group0++;
        } else {
            group1++;
        }

        for (int i = 1; i < str.length(); i++) {
            if (str.charAt(i) != str.charAt(i - 1)) {
                if (str.charAt(i) == '0') {
                    group0++;
                } else {
                    group1++;
                }
            }
        }

        System.out.println(Math.min(group0, group1));
    }
}