백준 알고리즘 1912번: 연속합

문제 정보

---

 

1912번: 연속합

 

핵심

---

요즘 많이 풀고 있는 Dynamic Programming, DP 알고리즘으로 문제를 풀이한다

정수 n의 개수가 최대 100,000이기 때문에 연속되는 수들의 합의 최대값을 구할 때 모든 경우의 수를 확인하는 것은

매우 비효율적인 방법이고, 심지어 수가 한개일 수도 있으며 연속되기만 한다면 모든 경우를 고려해야 하기 때문에 더더욱 사용하지 말아야 할 것이다

 

여기서 사용한 방법은 DP(동적 프로그래밍) 방법인데, 각각의 상태에서의 최대 합을 기록하며 풀이를 진행해 나가는 형식으로 문제를 해결할 수 있다

예를 들어, 입력한 값이 다음과 같다고 해보자 (N=10)

10

-4

3

1

5

6

-35

12

21

-1

 

우리는 연속된 수들의 합의 최대값을 구해야 하고, DP 알고리즘 풀이의 핵심은 점화식을 세우는 것이다

먼저 초기값을 세워보도록 하는데, 0번째 처음 위치에서는 자기 자신이 최대값을 가진다

여기서 dp 배열에서 인덱스의 의미는, i번째 위치에서 가질 수 있는 최대값(연속 or 자기자신)을 의미한다

dp[0] = numbers[0];

// dp[0] = 10

 

 

두번째 경우는 어떨까?

dp[1] = numbers[1] or 그전까지의 값(dp[0]) + numbers[1]

자신의 위치 전까지 연속되었던 값과 자기 자신의 합, 그리고 자기 자신을 비교했을 때 이 중 어떤 값이 큰지 비교하고 대입하면 된다

dp[1] = Math.max(dp[0]+numbers[1], numbers[1]);

// dp[0] = 10, numbers[1] = -4
// dp[0] + numbers[1] = 6

// 따라서 dp[1] = 6;

자기 자신만을 선택하는 방법(-4)보다는, 이전 연속되는 수들이 포함된 집합의 합(6)이 더 크기 때문에 더 큰 값을 dp[1]에 넣어준다

이를 dp[N-1]까지 반복해주면 각자 위치에서의 최대값 배열이 나오고, 여기서의 최대값이 연속된 수들의 합 중 가장 큰 합이다

dp[i] = Math.max(numbers[i], dp[i - 1] + numbers[i]);

 

 

예제 2의 경우에도 동일한 방식을 적용한다

2

1

-4

3

4

-4

6

5

-5

1

그냥 보기에는, 6 + 5인 11이 최대값일 것이라고 생각할 수 있지만

3 + 4 + -4 + 6 + 5 = 14가 최대값이다

 

위 방식을 적용한 해당 예제의 dp 배열은

2

3

-1

3

7

3

9

14

9

10

이 되므로, dp[7]의 14가 가장 큰 합임을 도출해낼 수 있을 것이다

 

 

풀이

---

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

class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int[] numbers = new int[N];
    int[] dp = new int[N];

    String[] input = br.readLine().split(" ");
    for (int i = 0; i < N; i++) {
      numbers[i] = Integer.parseInt(input[i]);
    }

    dp[0] = numbers[0];
    for (int i = 1; i < N; i++) {
      dp[i] = Math.max(numbers[i], dp[i - 1] + numbers[i]);
    }

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

 

Source Code on GitHub

---