[알고리즘] 백준 1912 연속합 -dp-

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

1912번: 연속합

 

 

 

백준 동적계획법1 (dp) 단계별 풀기에 있는 연속합 문제를 풀어봤습니다. ㅎㅎ

 

[입력 단계]

dp[] 에는 해당 인덱스까지의 최댓값을 담도록 합니다.

arr[] 에는 입력 숫자를 받습니다.

 

[반복문 단계]

현재 인덱스까지의 연속된 합과(dp[i-1] + arr[i]) 현재 값을(arr[i]) 비교합니다.

현재 인덱스보다 지금까지의 연속합이 더 작으면 최대값dp를 바꿔주도록 하고 아니면 현재인덱스까지의 연속된 합을 

dp로 세팅해줍니다.

 

 

 

풀이는 다음과 같습니다.

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] dp = new int[N];
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        dp[0] = arr[0];
        int max = arr[0];

        for (int i = 1; i < N; i++) {
            int n = dp[i - 1] + arr[i]; 
            dp[i] = Math.max(n, arr[i]); //이전의 최댓합과 현재 값의 합과 현재 값 중 큰걸 dp에 넣어줌
            max = Math.max(dp[i], max); //최댓값일경우 정답교체
        }
        System.out.println(max);
    }
}

https://github.com/mtjin/algorithm_practice/tree/master/%EB%B0%B1%EC%A4%80%201912%20%EC%97%B0%EC%86%8D%ED%95%A9%20-dp-

mtjin/algorithm_practice

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!