[백준] 1912 연속합 (JAVA)

문제 링크: 1912번: 연속합

 

 

난이도: 실버 2

 

 

소요 시간: 45분

 

 

문제:

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

 

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

 

 

입력:

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

 

 

출력:

첫째 줄에 답을 출력한다.

 

 

문제 이해:

문제 이해는 어렵지 않았을 것이다. 예제 입력 2을 기준으로 설명 하면,

1번째 줄에는 수열 N개

2번째 줄에는 수열이 주어진다.

 

이 수열중에 연속된 몇개의 수를 선택해 최대 값인 값을 출력하는 것이다.

10
2 1 -4 3 4 -4 6 5 -5 1

이때 가장 최대가 되는 연속값은  3+4+(-4)+6+5= 14가 되어 정답은 14이다.

 

 

구현 방향:

이 문제는 모든 경우를 일일이 탐색하지 않아도 된다.
연속된 부분 수열의 합 중 최댓값을 구할 때, 일정한 규칙이 존재하기 때문에
이를 이용하여 DP(동적 계획법) 방식으로 해결할 수 있다.

 

먼저, dp[i]를
“i번째 원소에서 끝나는 연속 부분합의 최댓값”
이라고 정의한다.

 

이때, i번째 위치에서의 최댓값은 두 가지 선택 중 하나로 결정된다.

1. 이전까지의 연속된 합에 현재 값을 더해서 이어가는 경우
   • 값: dp[i-1] + series[i]
2. 이전의 연속합은 모두 버리고, 현재 값 하나만으로 새로 시작하는 경우
   • 값: series[i]

여기서 중요한 규칙은 다음과 같다.

만약 이전에 연속된 값 + 현재 값 < 현재 값 이라면,
이전에 쌓아온 연속합은 오히려 방해가 되므로 이전 값들을 과감히 버려도 된다.

즉,
dp[i-1] + series[i] < series[i] 가 참이라면
dp[i]는 series[i]로 갱신하고,
그렇지 않다면 dp[i-1] + series[i]로 이어서 더하는 것이 이득이다.

 

정리하면, 각 i에 대해 다음과 같이 점화식을 세울 수 있다.

dp[i] = max(series[i], dp[i-1] + series[i])

 

이렇게 해서 dp 배열에 각 위치에서 끝나는 최대 연속합을 채워 넣고,
마지막에는 dp[0] ~ dp[N-1] 중 최댓값을 선택하면
그것이 곧 전체 수열에서 얻을 수 있는 최대 연속 부분합이 된다.

 

이를 코드로 그대로 구현하면 다음과 같다.

 

 

정답 코드:

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

public class Main {
    static int N;
    static int[] series;
    static int[] dp;
    static int max=Integer.MIN_VALUE;


    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());

        series=new int[N];
        dp=new int[N];


        StringTokenizer st=new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            series[i]=Integer.parseInt(st.nextToken());
        }
        //초기 세팅 끝

        dp[0]=series[0];

        for(int i=1; i<N; i++){
            //dp 점화식
            dp[i]=Math.max(dp[i-1]+series[i],series[i]);
            max=Math.max(dp[i],max);
        }

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


        //결과 출력
        System.out.println(max);


    }
}

 

 

마무리하며:

DP 문제는 결국 점화식을 어떻게 도출하느냐가 가장 큰 핵심이라고 느꼈다.
코드를 작성하는 능력보다, 문제의 구조를 분석하고
“이 문제를 어떤 규칙으로 분해할 수 있을까?”를 생각하는 능력이 훨씬 중요하기 때문이다.

 

하지만 한 번 점화식을 제대로 세워두면,

그 이후 구현 과정은 오히려 단순해지고 안정적이라는 점이 DP의 큰 장점이다.

 

이번 문제를 통해 점화식을 세우는 사고 과정의 중요성을 다시 한 번 깨달았고,
앞으로 더 많은 DP 문제를 경험하며 이러한 사고력을 꾸준히 키워야겠다고 느꼈다.

 

추가로 재귀식을 통한 시간 초과 코드이다. (모든 경우의 수를 전부 검사하기에 당연히 시간초과)

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

public class Main {
    static int N;
    static int[] series;
    static int max=Integer.MIN_VALUE;

    public static void solve(int count, int curSum){
        if(count==N-1) return;
        max= Math.max(max, curSum);

        // 연속합
        solve(count+1,curSum+series[count+1]);

        // 해당 수 버리기
        solve(count+1,series[count+1]);


    }
    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());

        series=new int[N];

        StringTokenizer st=new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            series[i]=Integer.parseInt(st.nextToken());
        }
        //초기 세팅 끝

        //탐색 시작
        solve(0,series[0]);

        //결과 출력
        System.out.println(max);


    }
}

 

 

감사합니다.