[백준] 1912. 연속합

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

1912번: 연속합

처음에는 좀 막혔는데 아이디어만 잘 생각하면 쉽게 풀 수 있다.

• dp[i]를 i를 포함한 연속 합의 최댓값이라고 했을 때, dp[i] = max(dp[i - 1], input[i])이다.
• 주의할 점은 dp[i]가 i까지의 최댓값이 아니라, i를 포함한 경우의 최댓값이다. 따라서 답은 dp[n]이 아니라, dp 배열에서의 최댓값이다.
• 입력 값으로 음수가 주어질 수 있다(ex, -1, -2, -3). 즉 dp 배열이 모두 음수로만 이루어질 수 있다(ex, -1, -1, -1). 따라서 answer의 초기 값을 0으로 하면 답이 0이 나와서 오답이 되므로, answer의 초기 값을 dp[1]로 해야 한다.

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

import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 시간 복잡도: O(N) = 100,000
public class Main {

    static int n;
    static int[] input;
    static long[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        input = new int[n + 1];
        dp = new long[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }

        // dp
        for (int i = 1; i <= n; i++) {
            dp[i] = Math.max(input[i], dp[i - 1] + input[i]);
        }

        // dp 배열에서 최댓값 찾기
        long answer = dp[1];
        for (int i = 2; i <= n; i++) {
            answer = Math.max(answer, dp[i]);
        }
        System.out.println(answer);
    }
}

 

dp 문제는 큰 문제를 작은 문제로, 즉 작게 생각하면 그 아이디어가 떠오르는 거 같다. 그리고 입력 값으로 음수가 주어질 수 있다면 반례를 생각해서 꼼꼼히 풀자.