[자바] 백준 2374 - 같은 수로 만들기 (java)

목차

문제 : boj2374

 

 

필요 알고리즘

• 분할정복 등
  
  • 뭘 해야하는지만 파악했다면, 풀이는 다양하다. 내 경우엔 분할정복으로 처리했다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  일단 뭘 해야하는지 생각해보자. 대충 A를 그렸을 때 아래처럼 그림이 나올꺼다.

 

  그럼 어차피 Add 연산만 있으니, 결국 모든게 최고지점을 향해 맞춰져야 한다.

 

  근데 Add를 하면 인접한 같은 수도 같이 증가하므로, 모든 A[1], A[2],... 에 대해 각각 계산하면 안되고, V자 모양으로 꺾여있는 부분의 가장 아래부터 시작해 평탄화(?) 작업을 해야 한다. 즉, 아래그림처럼 V 자 모양 꺾이는 부분부터 점점 올라오면서 주변에 인접한 동일한 값을 한꺼번에 증가시키면서 진행해야한다.

 

  위 말이 이해가 됬다면(?) 풀이는 다양하다. 결국 V자 모양인 부분을 찾으면 되므로, 그리디로 찾아도 되고 스택에 저장해가며 찾아도 된다. 내 경우엔 대강 구현이 제일 간편할 것 같아서 분할정복으로 처리했다.

 

  daq(int limit, int s, int e) 은 직전 최대 높이가 limit이니, limit까지 가려면 A[s], A[s+1], ... , A[e] 구간에서 Add 함수를 몇 번 불러야 하는지 리턴하는 함수이다. 그럼 이제 전체 구간에서 최대 높이를 찾고, 그 좌우 구간에 대해 daq를 진행하면 된다! 이하 주석에 로직을 써놨다.

private long daq(final int limit, final int s, final int e) {
    int max = 0;
    int maxIdx = 0;

    if (s<0 || e<0 || s>=n || e>=n || s>e) return 0;

    for (int i = s; i <= e; i++) {	// [s, e] 구간에 대해
        if (arr[i] > max) {	// 최대 높이와 최대 높이의 인덱스를 찾는다.
            max = arr[i];
            maxIdx = i;
        }
    }

    long answer = limit-max;	// limit까지 가려면 limit-max 만큼은 Add()를 불러야한다.
    answer += daq(max, s, maxIdx-1);	// maxIdx 기준 좌측 구간에 대해 분할정복!
    answer += daq(max, maxIdx+1, e);	// maxIdx 기준 우측 구간에 대해 분할정복!

    return answer;
}

 

  

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    int n;
    int[] arr;

    private void solution() throws Exception {
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        int max = 0;
        int maxIdx = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            if (arr[i] > max) {
                max = arr[i];
                maxIdx = i;
            }
        }
        long answer = 0;
        answer += daq(max, 0, maxIdx-1);
        answer += daq(max, maxIdx+1, n-1);

        System.out.println(answer);
    }

    private long daq(final int limit, final int s, final int e) {
        int max = 0;
        int maxIdx = 0;

        if (s<0 || e<0 || s>=n || e>=n || s>e) return 0;

        for (int i = s; i <= e; i++) {
            if (arr[i] > max) {
                max = arr[i];
                maxIdx = i;
            }
        }

        long answer = limit-max;
        answer += daq(max, s, maxIdx-1);
        answer += daq(max, maxIdx+1, e);

        return answer;
    }
}