[백준1912] 연속합 / Java

문제주소 :www.acmicpc.net/problem/1912

1912번: 연속합

---

<문제 설명>

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1

33

예제 입력 2

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2

14

예제 입력 3

5
-1 -2 -3 -4 -5

예제 출력 3

-1

 

<풀이법>

▒ 한줄 개념: 동적계획법 ▒ 

연속된 부분수열 중 합이 가장 큰 부분수열을 구하는 문제입니다.

양수는 어차피 더하면 커지기 때문에, 이 문제에서의 핵심은 음수입니다.

따라서, 음수를 데리고 갈 것이냐, 버리고 갈 것이냐로 나누면 됩니다.

음수를 포함한다는 것은 그 음수 앞의 모든 값을 포함한다는 것이므로, 음수를 포함한 앞의 모든 값을 다 더해서 양수가 나올경우, 그 음수를 포함하면 됩니다.

if(dp[i-1] + arr[i] > 0)
	dp[i] = dp[i-1] + arr[i];
else
	dp[i] = 0;

/*
예제: 10, -4, 3, 1, 5, 6, -35, 12, 21, -1

음수: -4, -35, -1

-4의 경우: 10 + (-4) = 6 / 가져감.
-35의 경우: 10 + (-4) + 3 + 1 + 5 + 6 + (-35) = -14 / 버림.
-1의 경우: 맨 마지막 -1, 필요없으므로 버림

dp = {10, 6, 9, 10, 15, 21, 0, 12, 32, 31}
*/

 

<<예외 사항>>

#1.

이 방법을 이용해 dp를 만들면 다음과 같습니다

dp = {10, 6, 9, 10, 15, 21, 0, 12, 32, 31}

그럼 여기서 마지막 31은 그 전인 32보다 작은 것을 확인할 수 있습니다.

이를 확장하여 마지막에 -x가 연속으로 나오는 경우가 있을 수 있으므로, 중간의 최댓값을 저장해두어야합니다.

2차원배열로 해도 되지만, 저는 따로 answer 변수를 이용하여 구현했습니다.

 

#2.

{-1,-2,-3,-4,-5} 와 같이 음수로만 이루어진 경우, 음수 중 최댓값이 정답이 됩니다.

따라서 이를 위한 변수를 따로 만들어놓고, 결과를 출력할 때 처리해주면 쉽게 처리할 수 있습니다.

 

 

<코드(Java)>

package Baekjoon;

import java.util.Scanner;

public class _1912_Continuous_Sum {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int[] arr = new int[size+1];
        int[] dp = new int[size+1];
        int minus = -1001;
        int answer = 0;

        for(int i = 1; i < size+1; i++){
            arr[i] = sc.nextInt();
            if(dp[i-1] + arr[i] > 0)
                dp[i] = dp[i-1] + arr[i];
            else
                dp[i] = 0;
                if(arr[i] > minus)
                    minus = arr[i];

            if(dp[i] > answer)
                answer = dp[i];
        }

        if(answer == 0)
            System.out.println(minus);
        else
            System.out.println(answer);
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest