관리 메뉴

차근차근

[백준 1912] 연속합 본문

대학교/Algorithm

[백준 1912] 연속합

SWKo 2020. 2. 1. 20:16

0. 제목

  • 백준 1912 연속합
  • BOJ 1912 연속합
  • C++ 1912 연속합

1. 문제

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


2. 풀이

  • DP 방식을 이용하였다.
  • 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 것이 목적이다.
  • 예를 들어, 배열의 값들이 10, 20, -100, -500, 700, 30  이라고 할 때, dp[1] = 10, dp[2] = 30, dp[3] = -70, dp[4] = -500, dp[5] = 700, dp[6] = 730 이다.
  • 이 배열 dp 의 원소 값들을 구하는 규칙은 다음과 같다.
  • 만약 dp[i]를 구하려고 할 때 dp[i-1] 가 음수라면 dp[i] = arr[i] 로 업데이트 해주고 양수라면 dp[i] = dp[i-1] + arr[i] 를 해주면 된다.
  • 그렇게 되면 dp[i] 는 arr[i] 를 포함한 가장 큰 합이 될 것이다.
  • 중요한 부분은 바로 다음 부분이다.
  • 앞서 구한 배열 dp의 원소값들 중 최댓값을 구해야 한다. 그것이 문제에서 요구하는 것이다.

3. 코드

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int n;
    int arr[100001];
    int dp[100001];//dp[i] 에는 arr[i] 를 포함하였을때의 최대 합을 담는다.
    int max;
    
    
    cin >> n;
    for(int i = 1;i <= n; i++){
        cin >> arr[i];
    }
    
    //max 로도 구현 가능
    dp[1= arr[1];
    max = dp[1];
    for(int i = 2; i <= n; i++){
        if(dp[i-1+ arr[i] > arr[i]) //if(dp[i-1]) > 0)
            dp[i] = dp[i-1+ arr[i];
        else
            dp[i] = arr[i];
    }
    
    //이 부분부터가 핵심
    max = dp[1];
    for(int i = 2; i <= n; i++){
        if(max < dp[i])
        max = dp[i];
    }
    //cout << dp[4]; 1, 2, 3, -100 일때 dp[4] = -96 이다. dp가 정답이 아니라 dp들을 비교하여 최대 값이 정답이다.
    cout << max << '\n';
    
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 11047] 동전 0  (0) 2020.02.05
[백준 10451] 순열 사이클  (0) 2020.02.02
[백준 1707] 이분 그래프  (0) 2020.02.01
[백준 11724] 연결 요소의 개수  (0) 2020.01.29
[백준 2750] 수 정렬하기  (0) 2020.01.28
0 Comments
댓글쓰기 폼