[백준] 1912번: 연속합 - java

문제

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

1912번: 연속합

 

접근법

연속된 수의 합을 보자마자 투포인터구나 하고 투포인터로 풀었는데 DP 문제였다. 그런데 채점현황을 보니 투포인터나 DP나 성능 차이는 크게 나지 않는 것 같다. 두 풀이 다 설명해보겠다.

 

투포인터

기본적인 투포인터 문제는 sum의 크기에 따라 오른쪽 포인터가 가리키는 값을 더해주거나, 왼쪽 포인터가 가리키는 값을 빼주어야 하지만 이 문제는 다르다.

 

누적해서 더해주다가 sum이 음수가 되었을 때 sum을 0으로 초기화해주면 된다. sum이 음수가 된다면 그 이후에 더해지는 수가 어떤 수이던 간에 그 sum은 최댓값이 아닐 것이다. 따라서  sum이 음수가 되면 0으로 초기화해준다.

 

글 쓰면서 생각난 건데 사실 왼쪽 포인터가 가리키는 값은 필요가 없어서 투포인터라고.. 할 수 있나? 싶기도 하다.. 그래도 아이디어는 투포인터에서 가져왔다!

 

코드

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

public class Main {

    static int n;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int end = 0;
        long sum = 0;
        long max = -1000;

        while (end < n) {
            sum += arr[end++];
            max = Math.max(max, sum);

            if (sum < 0) {
                sum = 0;
            }
        }

        System.out.println(max);
    }
}

 

DP

i번째 수의 입장에서 생각할 때 (i - 1까지의 최대 합 + i의 값)과 (i의 값)을 고르면 된다. 모든 수가 양수라면 더할수록 값이 커지겠지만 이 문제는 음수도 포함되기 때문에 이렇게 풀 수 있는 것이다. 이 내용을 토대로 점화식을 세우면 아래와 같다.

DP[i] = Math.max(DP[i - 1], DP[i - 1] + arr[i]) // i번째 까지의 최대 합

 

코드

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

public class Main {

    static int n;
    static int[] arr, dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        arr = new int[n];
        dp = new int[n];

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

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

        System.out.println(max);
    }
}

 

나는.. 투포인터가 편한듯 하다......