[백준] 1912: 연속합 - Java (DP)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

이 문제를 처음 마주하게 되었을 때는 투 포인터 방식으로 풀면 되는 거 아닌가? 왜 DP 문제인 거야? 라고 생각했다.

근데 질문 게시판에서 <투 포인터 방식에 대한 반례> 라는 글이 올라와 있었다.

 

그래서 DP 문제라는 확신을 가지고 DP 의 개념으로 문제를 보았다.

 

만약 dp[i - 1], 즉 이전 값이 0보다 작다면 그냥 자기 자신을 dp[i] 번째에 넣으면 된다는 것을 깨닳았다. 그리고 max 값을 저장하는 변수와 비교해서 더 큰 값을 변수에 저장하면 되는 것이었다. 왜냐하면 양의 정수 하나만 존재한다면 마이너스들은 볼 필요도 없을 테니까.

 

그리고 dp[i - 1] 이 0 보다 큰 양의 정수라면, dp[i - 1] 과 자신을 더한 값을 dp[i] 에 저장하고 max 값과 비교한다.

 

 

 

  풀이

 

 

package src.DP;

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

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

        // Input
        int N = Integer.parseInt(br.readLine());

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

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

        dp[0] = arr[0];


        // Main

        int answer = dp[0];

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

        }

        System.out.println(answer);

    }
}