백준 25214 - 크림 파스타 (자바 - 그리디)

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

25214번: 크림 파스타

 

* 문제 요약

크림 파스타를 먹다가 다음과 같은 문제를 생각해냈다.

비어있는 배열 A 가 있다. A 의 맨 뒤에 정수를 N 번 추가하려고 한다. 수를 그냥 추가하기만 하면 재미없으니 수를 추가할 때마다 1 <= i <= j <= |A| 를 만족하는 정수  i, j 에 대하여 Aj - Ai 의 최대값을 구하려고 한다.

|A| 는 배열 A 의 현재 길이를 뜻하고, Ai 는 i 번째로 추가한 정수를 뜻한다.

크림 파스타를 다 먹기 전에 이 문제를 풀어보자,

(크림 파스타는 그냥 억지로 끼워넣은 것 같은데)

 

* 입력

입력은 두 줄로 주어진다.

첫 번째 줄에는 배열에 추가하려는 정수의 갯수 N 이 주어진다.

두 번째 줄에는 A1 부터 AN 까지 N 개의 정수가 공백으로 주어진다.

 

* 출력

각 Ai 가 추가된 직후의 문제의 답 N 개를 공백으로 구분하여 출력한다.

 

* 제한

- 1 <= N <= 200,000

- 1 <= Ai <= 10^9

 

* 예시

 

* 해결 과정

A 배열에서 Aj 의 위치는 Ai 의 위치보다 항상 크거나 같다.

그러므로 Aj - Ai 를 구할 땐 Aj 의 값은 항상 Ai 와 같거나, 배열에서 Ai 의 오른쪽에 위치해 있어야 한다.

거기다 계산한 결과가 최대값이 되게 하려면 Aj 는 현재 배열에서 최대값에 해당하는 숫자를 저장해주는것이 좋고,

Ai 는 현재 배열에서 최소값이 저장되게끔 해주는것이 좋으나, j 의 위치가 i 와 같거나 i 보다 오른쪽에 있어야 한다는 조건 때문에 Aj 에 항상 현재 A 배열의 최대값이 저장되게끔 해주기가 어렵다.

 

즉, 문제풀이 조건상 순수하게 Aj  - Ai 가 최대값이 되게끔 해서 전체적인 최적해를 구하기는 어렵다는 뜻이다.

그렇기에 이 문제는 매 단계마다 조건에 맞게끔 Aj 와 Ai 를 초기화 해줄 필요가 있다.

Ai 의 경우 이전까지 입력된 숫자중 최소값과 현재 단계에서 입력된 숫자 중 더 작은 값을 저장시켜 주면 된다.

그런데 Aj 의 경우 최대값을 저장해주고자 할 때 만약 Ai 가 현재 단계에서 입력된 숫자가 최소값으로 저장되었다면 조건상 Aj 가 Ai 와 같은 위치에 있거나 더 오른쪽에 있어야 하기에 자연스럽게 Ai == Aj 가 될 수 밖에 없다.

 

이 경우 Aj - Ai 의 결과값은 0 이 되는데, 만약 조건에 맞는 다른 Aj - Ai 의 결과값을 구했을 때 그 값이 0 보다 더 큰값인 경우가 있을 수 있으므로, 이럴경우 이전 반복 단계에서 구했었던 다른 Aj - Ai 값으로 대체해줘야 한다.

좀 더 정확하게 말하자면, 현재 단계에서 구한 Aj - Ai 와 이전 단계에서 구한 Aj - Ai 중에서 더 큰값을 결과로 출력해주면 된다는 뜻이다.

 

자세한 로직은 아래와 같다.

1. 입력을 모두 받은 이후 최초의 최소값은 0 으로 설정해둔다.

2. 입력의 길이가 1 이상인 경우 결과를 출력하기 위한 배열의 첫번째 인덱스에 0 을 저장해준다.

왜냐하면 구하고자 하는 Aj - Ai 의 첫번째 값은 배열의 길이가 1일 때 구해지는데, 이 경우엔 반드시 Ai == Aj 가 성립되기 때문이다. 애초에 Ai 의 오른쪽에 다른 숫자가 존재하지 않는다는 뜻이다.

최소값은 입력으로 들어온 첫번째 값을 저장해둔다.

3. 입력의 길이가 2 이상인 경우 첫번째로 입력된 값을 number1, 두번째로 입력된 값을 number2 에 저장해두고 난 다음, 처음에 구했었던 결과값 0 과 number2 - number1 결과값을 비교해서 더 큰 값을 결과를 출력하기 위한 배열에 저장해준다.

이후 number1, number2 중 더 작은 값을 최소값으로 저장해둔다.

4. 입력의 길이가 2보다 큰 경우 아래와 같은 로직을 수행해준다.

  - 입력 배열의 인덱스 2 에서 부터 배열의 마지막까지 아래의 로직으로 반복문을 수행.

  - 기존에 구했던 최소값과 현재 입력값을 비교하여 더 작은 값을 최소값으로 저장. 

  - 현재 단계에서 입력된 값 - 최소값, 이전에 구했던 Aj - Ai 값 중 더 큰 값을 결과를 출력하기 위한 배열에 저장

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int count = Integer.parseInt(br.readLine());
        int[] resultArray = new int[count];
        int[] originArray = new int[count];
        String[] input = br.readLine().split(" ");

        for (int i = 0; i < input.length; i++) {
            originArray[i] = Integer.parseInt(input[i]);
        }

        int min = 0;
        if (input.length >= 1) {
            resultArray[0] = 0;
            min = originArray[0];
        }
        if (input.length >= 2) {
            int number1 = Integer.parseInt(input[0]);
            int number2 = Integer.parseInt(input[1]);
            resultArray[1] = Math.max(0, number2 - number1);

            min = Math.min(number1, number2);
        }
        if (input.length > 2) {
            for (int i = 2; i < count; i++) {
                min = Math.min(min, originArray[i]);
                resultArray[i] = Math.max(originArray[i] - min, resultArray[i - 1]);
            }
        }

        for (int i = 0; i < resultArray.length; i++) {
            bw.write(resultArray[i] + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

Aj 의 위치가 Ai 의 위치와 같거나 오른쪽에 위치해 있어야 한다는 조건으로 인해 자연스레 Aj - Ai 가 최대값이 되는 전체 최적해를 구하기가 힘들다.

대신 이후의 상황과는 상관없이 매 단계마다 바뀌는 배열의 상태를 기준으로 조건에 맞춰 최적화된 Aj - Ai 의 최대값을 구할수 있는 로직을 수행하고 있으므로 그리디 알고리즘에 해당된다.

 

또한 매 반복 단계마다 Aj - Ai 의 최대값을 구할 때 미리 이전에 구해둔 값과 현재 구한 값 중 더 큰 값을 결과를 출력하는 배열에 저장하는 방식으로 풀고 있는데, 이는 이전의 결과를 저장해두고 현재의 로직에 활용하는 메모이제이션 기법이 적용된 경우로서, 이 기법을 이용해 각 단계마다 조건에 맞춰 구할 수 있는 Aj - Ai 의 최대값을 구함으로서(매 단계마다 메모이제이션 기법을 통해 작은 문제 해결) 최종적으로 전체의 해답을 구하고 있으므로 다이나믹 프로그래밍 문제라고도 볼 수 있다.