[백준/C++] 1912 연속합

1912번: 연속합

문제의 내용

n개의 정수가 주어지고

연속되도록 나열된 정수들을 앞에서부터 순서대로 더하면서

연속적으로 더해졌을때 가장 큰 수를 구하는 문제 입니다.

연속된 숫자는 최소 1개이상 이어야 합니다.

(즉, 본인의 숫자 하나만으로도 가장 클 수도 있다는 뜻 / 예제 3번처럼)

 

예제 1번을 보자면

제시된 정수	계산 [기존+현재]	현재 계산된값	현재까지 최대값
10	최최숫자이므로 10	10	10
-4	10 + (-4)	6	10
3	6 + 3	9	10
1	9 + 1	10	10
5	10 + 5	15	15
6	15 + 6	21	21
-35	21 + (-35)	-14 연속적으로 더해서 커졌을때만이 조건 따라서 더작하졌으므로 연속X 초기화	21
12	기존초기화됬으므로 최초로 계산 시작 12	12	21
21	12 + 21	33	33
-1	33 + (-1)	32	33

위처럼 계산이 됩니다.

처음에 문제를 한참 이해하지 못해서 결국 풀이를 참고하게 되었습니다. 풀이를 보고나니 쉬운데..

문제를 제대로 파악하는부분이 너무 어려웠던 듯 합니다.

 

중요하게 봐야 할 것은

• 연속적으로 더해져야함.
• 즉, 계속더해지다가 현재까지의 최대값이 더작하지는순간 연속은 초기화 됨.
• 계산의 시작부분 or 초기화후다시시작되는부분은 처음 계산 = 본인의 값
• 현재까지 더해진값은 계속 따로 저장해둬야함

#include <iostream> // 입출력
#include <algorithm> // max() 함수사용

#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);
#define MAX 100001 // 문제에서 제시한 최대 크기

using namespace std;

int qarr[MAX], arr[MAX]; 
// 최대크기제한이있는 배열 2개
// qarr은 입력받은 정수를 저장할 배열
// arr은 계산에 사용될 qarr과 같은배열
// 따로 0으로 초기화 안해도 ok

int main()
{
    fastio; // 입출력 단축 매크로
    int n; // 배열의 총갯수를 입력받을 변수
    cin >> n; 
    for (int i = 0; i < n; i++) // 횟수만큼 반복
    {
        cin >> qarr[i]; // 제시된 문제의 정수를 순서대로 배열에 저장 0 ~ n 까지
        arr[i] = qarr[i]; // 계산에 사용할 arr 복사해서 대입하기.
    }
    int Sum = arr[0]; // 순차적으로 더해나갈 것 이기 때문에 합계변수는 우선 첫번째 배열로 저장
    for (int i = 1; i < n; i++) // 위에서 입력받은 n 횟수만큼 반복문을 진행
    {
        arr[i] = max(arr[i], arr[i-1]+ arr[i]); // algorithm 의 max() 함수를 사용!
        // max(a, b) 함수는 매개변수 두개중 큰것의 값을 반환해주는 함수.
        // 따라서 arr[i](i번째) , arr[i-1] + arr[i](i-1번째,즉바로앞순서 + 배열 i번째)를 더한값을 비교.

        if (arr[i]>Sum) // 만약 arr[i]번째의값이 Sum(arr[0]번째의값이들어있는변수)보다 크다면
        {
            Sum = arr[i]; // Sum의 값을 더큰 arr[i]의 값으로 바꿔준다.
        }
        // 위의 계산들을 배열의 시작부터 끝까지 반복해주게되면
        // 배열중 연속적으로 더해져서 제일 큰값이 반환이 된다.
    }
    cout << Sum << endl;
    return 0;
}

코드길이 최대한 줄이기!!!!!

#include <iostream>
#include <algorithm>
#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);
using namespace std;
int qarr[100001], arr[100001];
int main()
{
    fastio;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> qarr[i];
        arr[i] = qarr[i];
    }
    int Sum = arr[0];
    for (int i = 1; i < n; i++){
        arr[i] = max(arr[i], arr[i-1] + arr[i]);
        if (arr[i]>Sum)
            Sum = arr[i];
    }
    cout << Sum << endl;
    return 0;
}

Ps. 숫자를 더했을때의 값들을 하나하나 저장해서 저장값을 배열로만들고 sort로 정렬해서 제일큰수인 끝을 구하려고했으나..그게 아니었습니다..