[백준 *Java] - 연속합 (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보다 작거나 같은 정수이다.

출력
첫째 줄에 답을 출력한다.

 

 

[접근방식]

DP테이블에 무얼 담아야할까? 

작은 문제를 풀어야 큰 문제를 풀수 있는 DP문제이니

일단 N개로 이루어진 수열을 작게 만들어봅니다.

일단 -가 들어오는 값은 '+' 연산에서 벗어나는 게 좋을 거 같다라고 생각을 했는데,

들어온 수열이 - 값이 많거나 전체가 다 - 값이라면? - 값이라도 출력을 해줘야하니 이건 안될 거 같다.

10 -4 = 6

-4 3 = -1

3 1 = 4

5 6 = 11

6 -35 = -29

-35 12 = 23

12 21 = 33

21 -1 = 20

이렇게 사고를 하는 게 처음부터 전체를 바라보는 행위인 거 같다.. Pass....

10 -4 = 6 이게 N이 2 수열일 때, 가장크다.

10 -4 3 = 10 -4 = 6 

                  -4 3 = -1

                 10 -4 3 = 9

이렇게 봐서는, -가 들어가도 - 수의 이전 수가 큰 수라고 하면 충분히 연속된 합을 만들어도 커질 것이다.

예제 2를 보면,

2 1 -4 3 4 -4 6 5 -5 1 을 각 N 번째 수열만큼 합이 최대인 값을 넣으면 됩니다.

2 3  3 3 7  7  9 14 9 10 즉, 최대값은 14가 될 것입니다.

DP 로는 최대 합 수를 넣으면 될거 같습니다

for문을 두개를 사용해서 이제 구현을 하면 될 거 같습니다.

 

생각대로 로직을 짰지만, 시간초과로 틀렸습니다..

실패한 코드

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

public class Main {

    static int DP[]; // 해당 인덱스 위치의 최대합을 담습니다.

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

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

        DP[0] = target[0]; // N이 1 수열일 땐, 당연히 1이 최대 합.
        int max = DP[0];
        for (int i = 1; i < target.length; i++) {
            int accumulate = target[i];
            for (int j = i-1; j >= 0; j--) {
                    accumulate += target[j];
                    max = accumulate > max ? accumulate : max;
            }
            DP[i] = max;
        }

        System.out.println(DP[N-1]);
    }
}

 

이중 포문이 아닌,

Math.max 를 이용하여 풀면 for문 하나로만 이용하여서 구할 수 있었습니다.

뭔가 효율적으로 코드를 작성하지 못했던 게 아쉬웠던 거 같습니다.

성공한 코드

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

public class Main {

    static int DP[]; // 해당 인덱스 위치의 최대합을 담습니다.

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

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

        DP[0] = target[0]; // N이 1 수열일 땐, 당연히 1이 최대 합.
        int max = DP[0];
        for (int i = 1; i < target.length; i++) {
            DP[i] = Math.max(target[i], target[i] + DP[i-1]);
            max = Math.max(DP[i], max);
        }
        System.out.println(max);
    }
}