[백준 1912번] 연속합 with Java

guswls·2024년 5월 5일

DP 백준

알고리즘

목록 보기

17/39

문제

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

코드

import java.util.*;
import java.io.*;

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

class Main {

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

		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

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

			max = Math.max(dp[i], max);
		}

		System.out.println(max);
	}
}

문제 이해

문제 그대로 이해하면 된다.
어떠한 수열이 입력으로 주어질 때, 연속적인 영역을 선택해서 가장 큰 합을 구하면 된다.

풀이 방법

이 문제는 dp로 해결해야한다. 브루트포스같은 방법을 사용하면 시간초과가 발생한다.
이 문제에 활용된 dp에 대한 표는 많다. 여기서는 간략히 설명하겠다.
우선 연속적인 값들의 합을 구하는 방법은 크게 두가지이다.
1. 이전까지 연속적인 합에 현재 숫자를 더하는 방법
2. 이전까지의 연속적인 합을 버리고 현재 숫자만 택하는 방법
예를 들어 1 -6 10이라는 수열이 있다고 생각하자.
여기서 세번째 시점에서의 연속 합을 구하려면 1) 10만 선택하거나 2) 이전 수열의 합인 -5에 10을 더한 5를 선택하거나 두가지이다.
여기서 이전 수열의 최대 합은 dp[i-1]이다.
이를 점화식으로 표현하면 다음과 같다.

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

핵심 포인트

dp에 대한 이해, 그리고 연속적인 합의 최대값을 구하기 위한 방법을 이해하고 있어야 한다.
이전꺼를 선택하는 경우와 이전꺼를 버리는 경우 사이의 최대값을 구한다고 생각하자.

보완할 점 / 느낀 점

호기롭게 이중 for문으로 max값을 갱신시키는 방법으로 코드를 짜고 제출했다가 시간초과를 맞았다.
입력 크기가 200,000이기 때문에 O(n^2)을 하면 40,000,000,000, 즉 4백억이라는 시간이 걸린다. 제한 시간에 따르면 최대 1억개의 루프 안에 해결해야하기 때문에 브루트포스로는 해결할 수 없다.
최근 그냥 시간복잡도를 생각하지 않고 빡구현으로만 해결하고 있었는데, dp도 많이 연습해야겠다.