M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 1912 - 연속합(maximum sum)

최대 1 분 소요

문제

백준 1912 - 연속합 풀러가기

문제 분석

이 문제도 유명한 문제다 maximum sum이라고 한다.

한 시점에서 과거의 maximum 값은 변함 없으므로, dynamic programming 으로 풀 수 있다.

한 시점의 값을 더했을 때, 이전의 연속합보다 작아진다면 현재 시점에서 새로운 연속을 시작하는게 낫다. 이를 이용하여 문제를 풀면 된다.

문제 풀이(C++)

  1. 전체 코드

    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
    #include <cstdio>
    #include <vector>
    #include <algorithm>
     
    using namespace std;
     
    int main() {
        int n;
     
        scanf("%d", &n);
     
        vector<int> a(n);
        vector<int> d(n);
     
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
     
        d[0] = a[0];
     
        for (int i = 1; i < n; i++) {
            if (d[i - 1] + a[i] < a[i]) {
                d[i] = a[i];
            }
            else {
                d[i] = d[i - 1] + a[i];
            }
        }
     
        printf("%d", *max_element(d.begin(), d.end()));
     
     
        return 0;
    }
    		cs

연관 문제






아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고