boj2879 코딩은 예쁘게_java

문제

백준이는 한 작은 회사에 취직했다. 이 회사에서 백준이는 소스 코드의 뒤죽박죽인 인덴트를 고치고 있다. 인덴트는 각 줄을 탭 키를 이용해 들여 쓰는 것을 말한다. 다행히 백준이가 사용하는 편집기는 연속된 줄을 그룹으로 선택하고, 여기에서 각 줄의 앞에 탭을 추가하거나, 삭제할 수 있다. 백준이를 도와 코드의 뒤죽박죽인 인덴트를 예쁘게 고치는 방법을 생각해보자.

줄의 개수 N과 각 줄의 앞에 있는 탭의 개수와 올바른 탭의 개수가 주어진다. 이때, 한 번 편집을 할 때, 다음과 같은 명령을 수행할 수 있다.

• 연속된 줄을 그룹으로 선택한다.
• 선택된 줄의 앞에 탭 1개를 추가하거나 삭제한다.

위의 두 명령을 모두 수행하는 것이 하나의 편집이며, 선택된 줄의 개수와는 상관이 없다. 만약, 선택한 줄 중에 단 한 줄이라도 탭이 없을 경우에는, 탭을 삭제하는 명령을 수행할 수 없다.

백준이가 몇 번 편집 만에 코드의 인덴트를 올바르게 고칠 수 있는지 구하는 프로그램을 작성하시오. 이때, 편집 회수의 최솟값을 구해야 한다.

입력

첫째 줄에 줄의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 현재 줄에 있는 탭의 개수가 주어지며, 1번째 줄부터 순서대로 주어진다. 탭의 개수는 0보다 크거나 같고, 80보다 작거나 같은 정수이다. 셋째 줄에는 각 줄의 올바른 탭의 개수가 주어진다. 1번째 줄부터 순서대로 주어지며, 이 값도 0보다 크거나 같고, 80보다 작거나 같은 정수이다.

출력

첫째 줄에 코드의 인덴트를 올바르게 고치는 편집 회수의 최솟값을 출력한다.

나의 풀이

• 기존 풀이 방식은 차이값을 가지는 그룹에서 가장 작은 index를 뽑아서 경우를 구하는 것이었는데 이렇게 하면 1 1 1 1 1→ 5 3 1 3 5 를 할때 중간 과정에서 문제가 생긴다.
• 문제발생
  • 연산을 진행할 그룹의 max 값을 구해서 그걸 더하는 방식으로 풀었는데, 왜인지 모르게 계속 에러가 났다.
• 해결방법
  • 각종 코드들을 참고하였다.
  • 더하거나 빼야하는 target 값이 증가하는 경우에는 prev를 계속 체크하고,
    감소하는 경우에는 이 차이값을 answer에다가 더해주었다. 그리고 마지막에 prev를 더해주었다.
  • 부호가 바뀌는 경우에는 answer에 prev를 더해주었다.
• prev를 더해주는거나 max값을 구해서 해주는거같은 생각에서 출발하였으나 max 값은 구하는 과정에서 반례가 있는 것 같다.
• 핵심 코드

  if(N>1) {
              prev = target[0];
              for (int i = 1; i < N; i++) {
                  if(prev*target[i]<0){
                      answer += Math.abs(prev);
                  }else if(Math.abs(prev)>=Math.abs(target[i])){
                          answer += Math.abs(prev)-Math.abs(target[i]);
                  }
                  prev = target[i];
              }
          }else{
              answer = target[0];
          }
          answer += Math.abs(prev);

• 전체 코드

  package Baekjoon.java.silver;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.*;
  import java.util.stream.Collectors;
  
  public class boj2579 {
  
      public static void main(String[] args) throws Exception {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N = Integer.parseInt(br.readLine());
          int[] target = new int[N];
          int prev = 0;
          int answer = 0;
  
          StringTokenizer st = new StringTokenizer(br.readLine());
          for (int i = 0; i < N; i++) {
              target[i] = Integer.parseInt(st.nextToken());
          }
          st = new StringTokenizer(br.readLine());
          for (int i = 0; i < N; i++) {
              target[i] = Integer.parseInt(st.nextToken())-target[i];
          }
          if(N>1) {
              prev = target[0];
              for (int i = 1; i < N; i++) {
                  if(prev*target[i]<0){
                      answer += Math.abs(prev);
                  }else if(Math.abs(prev)>=Math.abs(target[i])){
                          answer += Math.abs(prev)-Math.abs(target[i]);
                  }
                  prev = target[i];
              }
          }else{
              answer = target[0];
          }
          answer += Math.abs(prev);
          System.out.println(answer);
      }
  
  }

결과