백준 2879(JAVA)

문제

풀이

그리디 알고리즘으로 문제자체 푸는법은 어렵지않으나 나는 너무 안일하게 생각했던 나머지 2번 틀렸다.
그리디 알고리즘 자체가 '이 문제는 그리디 알고리즘으로 푸는 것이다'라는 것을 깨닫는게 어려운거지, 깨닫고나면 푸는법은 어렵지 않은 것 같다.

하나의 편집은 연속된 줄을 그룹으로 탭을 하나 추가하거나 삭제할수 있다.
이 편집의 횟수를 최소화하라는 문제이다.
일단 입력되는 두줄의 차이를 먼저 계산했다.(모두 0 으로 바꾸는게 목적이므로)

4
5 4 5 5
1 5 0 1

4 -1 5 4

가 된다.
일단 한번의 편집에 탭을 추가하거나 뺄수 있으니 음수 양수로 나눠야겠다는 생각을 했다.
(4)
(-1)
(5, 4)
로 나뉘게 된다.

한번의 편집은 여러줄을 그룹으로 선택할수 있기에
여러줄을 한번에 1씩 더하거나 뺄수 있다.

• (4)그룹의 모든 합을 0으로 만드려면
  4번의 편집을 걸쳐 0으로 바꿀수있고

• (-1)그룹의 모든 합을 0으로 만드려면
  1번의 편집으로 0 으로 바꿀수있고

• (5, 4)그룹의 모든합을 0으로 만드려면
  5번의 편집으로 0 으로 바꿀수있다.

총 10번!

즉, 양수 음수를 기준으로 최초에 구분한 그룹마다 편집을 가하는데, 편집을 하는 도중에도 그룹이 나뉠수있다. 무슨말이냐면

5
1 1 1 1 1
5 3 2 3 2

예시는 차이를 구하면 -4 -2 -1 -2 -1로
음수 양수 그룹으로 구분하면
(-4, -2, -1, -2, -1)하나이다.
하나의 편집을 가하면
(-3, -1, 0, -1, 0)이 된다.
이때 (-3, -1), (-1)이런식으로 다시 그룹이 생기게 된다.(우리는 최소의 편집횟수를 구해야하므로 그룹을 할수있으면 그룹지어서 편집을 무조건 해야한다.)

이부분을 고려하면서 코드를 작성하면 문제를 풀수있다!(나는 이부분을 생각못해서, 두번이나 틀렸다.)

코드

package baekjoon.그리디;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main2879 {
    static int N;
    static int[] diff;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        diff = new int[N];
        int[] input = new int[N];
        int[] output = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++){
            input[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++){
            output[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i < N; i++){
            diff[i] = input[i] - output[i];
        }

        System.out.println(fixIndent());
    }
    static int fixIndent(){
        int count = 0;

        List<List<Integer>> group = new ArrayList<>();
        for(int i = 0; i < N; i++){
            group.add(new ArrayList<>());
        }
        int num = 0;
        int before = 0;
        int after = 0;
        if(diff[0] > 0) before = 1;
        else if(diff[0] == 0) before = 0;
        else before = -1;
        group.get(num).add(diff[0]);

        for(int i = 1; i < diff.length; i++){
            if(diff[i] > 0){
                after = 1;
            }else if(diff[i] == 0){
                after = 0;
            }else{
                after = -1;
            }
            if(before == after){
                group.get(num).add(diff[i]);
            }else{
                num++;
                group.get(num).add(diff[i]);
            }
            before = after;
        }
        for (List<Integer> integers : group) {
            if(integers.size() == 0) break;
            int sum = integers.stream().mapToInt(Integer::intValue).sum();
            while(sum != 0){
                int startIdx = 0;
                for(int i = 0; i < integers.size(); i++){
                    if(integers.get(i) != 0) {
                        startIdx = i;
                        break;
                    }
                }
                for(int i = startIdx; i < integers.size(); i++){
                    if(integers.get(i) != 0){
                        if(integers.get(i) > 0){
                            integers.set(i, integers.get(i) - 1);
                        }else{
                            integers.set(i, integers.get(i) + 1);
                        }
                    }else break;
                }
                sum = integers.stream().mapToInt(Integer::intValue).sum();
                count++;
            }
        }

        return count;
    }
}