[백준 | Java Silver I] (#1912) 연속합

문제

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

---

접근

완전 탐색으로 풀면 주어진 테스트 케이스 3개는 통과하지만 시간 초과가 떠서 실패하는 문제였고, dp를 통해 풀어야 했다. 

 

💡DP적 접근

1. 각 위치에서 끝나는 최대 부분합을 저장한다. 
2. 현재 위치에서 끝나는 최대 부분합은 이전 위치에서 끝나는 최대 부분합에 현재 값을 더한 것과 현재 값 자체 중 큰 값이 된다. 
3. 전체 배열을 순회하며 각 위치에서의 최대 부분합을 갱신해서 전역 최대값을 구한다.

 

DP 배열을 사용하여 dp[i]를 i번째 요소로 끝나는 최대 부분합으로 정의한다. 점화식을 나타내면 아래와 같다. 

dp[i]=max⁡(dp[i−1]+nums[i],nums[i])

 

그리고 전역 최대값을 추적하는 변수 max를 사용하여, 최종적으로 최대 부분합을 찾는다. 

 

이렇게 풀면 완전탐색은 O(n^2)인 것에 비해 dp는 O(n)으로 훨씬 효율적이다. 

 

---

첫번째 코드 - 실패: 완전 탐색(시간 초과)

package week11.baek.july19.baek;

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

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

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

        int max = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = i; j < n; j++) {
                count += nums[j];
                if(max < count) max = count;
            }
        }
        System.out.println(max);
    }
}

 

최종 코드 - dp 사용

package week11.baek.july19.baek;

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

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

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

        // DP 배열 초기화
        int[] dp = new int[n];
        dp[0] = nums[0];
        int max = dp[0];

        for (int i = 1; i < n; i++) {
            //지금까지의 연속합 + 현재 값 vs 현재 값
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            if(dp[i] > max) max = dp[i];
        }

        System.out.println(max);
    }
}