[백준] - 1912 연속합

dp bottom up 방식을 이용한 코드

package christmas.view;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class bj_1744 {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());

        String[] arr = br.readLine().split(" ");
        int result = 0;

        int[] dp = new int[n+1];

        dp[1]= Integer.parseInt(arr[0]);

        if (allNegative(arr)){
            result= Arrays.stream(arr).mapToInt(Integer::parseInt).max().orElse(0);
            System.out.println(result);
            return;
        }

        for (int i = 2; i <= n; i++){
            int now = dp[i-1] + Integer.parseInt(arr[i-1]);
            if(now >= 0){
                dp[i] = dp[i-1] + Integer.parseInt(arr[i-1]);
            } else {
                dp[i] = 0;
            }
        }

        result = Arrays.stream(dp).max().getAsInt();
        System.out.println(result);

    }

    private static boolean allNegative(String[] arr) {
        for (String num : arr) {
            int i = Integer.parseInt(num);
            if (i > 0){
                return false;
            }
        }
        return true;

    }


}

• 연속합을 구할때 모두 음수거나 0인 경우를 대비해서 해당 배열의 수가 모두 음수인지를 판단하는 메서드를 만들어 true를 반환하면 이때 가장 큰 수를 출력하게 했다. (반례 1 - 모두 음수이거나 0인 경우를 처리) 
• 풀이 방식 고민
  • 그리고 이제 dp를 이용해서 해당 수를 찾아갔다. 
  • 우선 bottom up 방식(=반복문)을 사용해 dp를 채워가는 방식으로 진행했다.
  • dp[1] = arr[0]  값을 대입해 초기값을 설정해주었다. (dp[0]부터 시작할 경우 dp[0]=arr[0])

 

배열을 이용한 arr와 dp 데이터 예시

• dp에 저장하는 값을 최대값이 될수 있는 경우로 구성했다.
• 그래서 앞에서 구한 n개의 연속합보다 현재 값을 더한 값이 0보다 작을 땐 dp[index]를 0으로 초기화해줬다.
  • 이렇게 하지 않으면 연속된 몇개의 수를 더했을 때 최대값이 나오지 않기 때문이다.
  • 음수를 누적해서 더하게 되면 33이. 아니라 -14, -2, 19로 최대값이 21이어야 하는데 12+21을 하면 33이 나오기 때문에 이 부분을 0으로 초기화해주어야 한다.
• 현재 index의 바로 직전까지 더해준 값을 dp[index-1]에 두고 내 현재 index에 저장된 arr값을 더해줬을 때 0보다 크거나 같은 경우라면 계속 값을 더해준다.
  • 이때는 음수를 고려하지 않는다. 왜냐 arr[1]인 경우를 보면 -4지만 직전 누적합이 10이기 때문에 6이라는 수가 나온다. 이 경우라면 상관 없기 때문이다. 
• 그리고 마지막으로 dp에 저장한 값들을 모두 싹 돌아서 가장 큰 값을 출력해주면 그게 정답이 된다.

 

합을 누적하면서 풀지 않는 방법

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        String[] arr = br.readLine().split(" ");
        int result = Integer.MIN_VALUE;
        int sum = 0;

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(arr[i]);
            sum += num;
            result = Math.max(result, sum);
            if (sum < 0) {
                sum = 0;
            }
        }

        System.out.println(result);
    }
}

• 변수를 선언해서 값을 비교해가면서도 가능하다.