[BOJ]1912번: 연속합(java, c++)

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

1912번: 연속합

 

 

방법 1: Top-down

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
 
    static int[] arrNumbers;
    static int[] arrTempSerialSum;
    
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int iTotal = Integer.parseInt(br.readLine());
            arrNumbers = new int[iTotal];
           arrTempSerialSum= new int[iTotal];
 
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            for (int i = 0; i < iTotal; i++) {
                arrNumbers[i] = Integer.parseInt(st.nextToken());
            }
            
            System.out.println(calculate(iTotal - 1, arrNumbers[0]));
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    public static int calculate(int i, int iResultMax) {
        if (i == 0) {
           arrTempSerialSum[i] = arrNumbers[i];
            return iResultMax;
        }
        
        iResultMax = calculate(i - 1, iResultMax);
        
       arrTempSerialSum[i] = Math.max(arrTempSerialSum[i - 1] + arrNumbers[i], arrNumbers[i]);
        
        if (iResultMax < arrTempSerialSum[i]) {
            iResultMax = arrTempSerialSum[i];
        }
        
        return iResultMax;
    }
}

 

방법 2: Bottom-up

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int iTotal = Integer.parseInt(br.readLine());
            int[] arrNumbers = new int[iTotal];
            int[] arrTempSerialSum = new int[iTotal];
            
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
            for (int i = 0; i < iTotal; i++) {
                arrNumbers[i] = Integer.parseInt(st.nextToken());
            }
 
            
            arrTempSerialSum[0] = arrNumbers[0];
            int iResultMax = arrTempSerialSum[0];
            
            for (int i = 1; i < iTotal; i++) {
                arrTempSerialSum[i] = Math.max(arrTempSerialSum[i - 1] + arrNumbers[i], arrNumbers[i]);
                
                if (iResultMax < arrTempSerialSum[i]) {
                    iResultMax = arrTempSerialSum[i];
                }
            }
            
            System.out.println(iResultMax);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 

c++소스

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // 입력
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
 
    /*
        점화식 : D[i] = i번째 수로 끝나는 가장 큰 연속합
        
        --> D[i - 1] >= 0 이라면 연속합 계산.
        --> D[i - 1] <  0 이면 A[i]로 새로운 연속합 시작.
    */
    vector<int> S(n);
    S[0] = A[0];
    for (int i = 1; i < n; i++)
    {
        if (S[i - 1] >= 0)
        {
            S[i] = S[i - 1] + A[i];
        }
        else
        {
            S[i] = A[i];
        }
    }
 
    // 가장 큰 연속합 출력
    cout << *max_element(S.begin(), S.end());
 
    return 0;
}

 

바텁업이 더 효율적이다.

 

 

TIP1

A[N] 까지 더한 연속합을 D[N]이라 하자.

D[N - 1] + A[N] 와 A[N] 의 크기를 비교하여 

더 큰 것을 D[N]에 대입한다

 

 

TIP2

D[끝값]이 가장 큰 값이 아닐 수 있다!