관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/DP

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

막무가내막내 2020. 6. 18. 16:56
728x90

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

 

1912번: 연속합

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

www.acmicpc.net

 

 

 

백준 동적계획법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

알고리즘 문제풀이 연습. Contribute to mtjin/algorithm_practice development by creating an account on GitHub.

github.com

 

 

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

728x90
Comments