[Baekjoon Online Judge] 백준 1912번 연속합(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1912번 연속합

(C++, Python)

(글쓴날 : 2020.04.15)

 

---

* Baekjoon Online Judge, 백준 1912번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1912번 연속합

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1912

1912번: 연속합

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

n개의 정수로 이루어진 수열이 주어지고, 해당 수열 중 최댓값이 되는 연속합을 구하는 문제입니다.

 

저의 경우, 동적 계획법을 적용하였으며, C++과 Python을 사용했습니다.

먼저, n이 1일 경우는 값이 하나이면서 최댓값이 되므로 예외 처리를 해두었고,

이후 수열을 탐색할 때 더해야 할 수가 음수일 경우에 이전까지의 합이 양수일 경우와 음수일 경우로 분기하여 만약, 양수라면 합이 0보다 커지는지 작아지는지 따져 memoization할 값을 정했고, 음수라면 이전 합과 더하지 않고 더해야 할 값 자체를 memoization했습니다.

반대로 더해야 할 값이 양수였다면, 이전 합이 양수일 경우 추가로 더해 memoization하고, 음수일 경우 더해야 할 값 자체를 memoization했습니다.

 

이후, memoization될 때마다 memoization된 값과, 연속 합의 최댓값을 저장해 놓기 위해 미리 만들어 놓은 변수의 값을 계속 비교해가며 저장해, 최종적으로 최댓값이 되는 연속합을 출력하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    cin >> n;
 
    vector<int> nums(n, 0);
    vector<int> memoization(n, 0);
    int maxNum = -1001;
 
    for (int i = 0; i < n; i++)
        cin >> nums[i];
 
    for (int i = 0; i < n; i++)
    {
        if (!i)
        {
            maxNum = memoization[0] = nums[0];
            continue;
        }
 
        if (nums[i] < 0)
        {
            if (memoization[i - 1] > 0)
            {
                if (memoization[i - 1] + nums[i] > 0)
                    memoization[i] = memoization[i - 1] + nums[i];
                else
                    memoization[i] = nums[i];
            }
            else
                memoization[i] = nums[i];
        }
        else
        {
            if (memoization[i - 1] > 0)
                memoization[i] = memoization[i - 1] + nums[i];
            else
                memoization[i] = nums[i];
        }
 
        if (maxNum < memoization[i])
            maxNum = memoization[i];
    }
 
    cout << maxNum;
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
n = int(input())
nums = list(map(int, input().split()))
memoization = [0] * n
maxNum = -1001
 
for i in range(n):
    if not i:
        memoization[0] = maxNum = nums[0]
        continue
 
    if nums[i] < 0:
        if memoization[i - 1] > 0:
            if memoization[i - 1] + nums[i] > 0:
                memoization[i] = nums[i] + memoization[i - 1]
            else:
                memoization[i] = nums[i]
        else:
            memoization[i] = nums[i]
    else:
        if memoization[i - 1] > 0:
            memoization[i] = nums[i] + memoization[i - 1]
        else:
            memoization[i] = nums[i]
        
    if maxNum < memoization[i]:
        maxNum = memoization[i]
 
print(maxNum)

---