[BAEKJOON] 1912번 연 속 합

문 제

 

소 스  코 드

#include <iostream>
#include <algorithm>

constexpr int MIN_INT{ -1'000'000'000 };

int main() {

	int N;
	std::cin >> N;

	int *seqadd{ new int[N] };
	int *dp{ new int[N] };
	std::fill_n(dp, N, 0);

	for (int i = 0; i < N; ++i) std::cin >> seqadd[i];

	dp[0] = seqadd[0];
	int maxnum{ dp[0] };
	for (int i = 1; i < N; ++i) {
		dp[i] = std::max(dp[i - 1] + seqadd[i], seqadd[i]);
		maxnum = std::max(maxnum, dp[i]);
	}


	std::cout << maxnum;

	delete[] dp;
	delete[] seqadd;

	return 0;
}

 

풀 이

 

• A : { 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 }

  dp[0] : 10

  dp[1] : Max( dp[0] + A[1], A[1] )

  dp[2] : Max( dp[1] + A[2], A[2] )

  dp[3] : Max( dp[2] + A[3], A[3] )

                    ...

  dp[N - 1] : Max ( dp[N - 2] + A[N - 1], A[N - 1] )

• dp[N-2] + A[N-1]과 A[N - 1] 중에 더 큰 수를 찾는 이유는 이전의 누적값 보다 현재 값이 크다면,
  연속되는 과정에 문제가 있다는 뜻이기 때문에 현재 수에서 다시 진행하기 위하여 현재 값으로 누적값을 변경한다.

• 만약, 무조건 끝에 있는 누적값이 MAX가 아니기 때문에, 누적값 중에 최댓값을 알기 위하여 비교하여 진행한다.

 

주 의 점

#include <iostream>
#include <algorithm>

constexpr int MIN_INT{ -1'000'000'000 };

int main() {

	int N;
	std::cin >> N;

	int *seqadd{ new int[N] };
	int *dp{ new int[N] };
	std::fill_n(dp, N, 0);

	for (int i = 0; i < N; ++i) std::cin >> seqadd[i];
	int addmax{ MIN_INT };
	int temp;

	for (int i = 0; i < N; ++i) {
		dp[i] = seqadd[i];
		temp = dp[i];

		for (int j = i + 1; j < N; ++j) {
			dp[i] = dp[i] + seqadd[j];
			temp = std::max(temp, dp[i]);
		}
		addmax = std::max(addmax, temp);
	}

	std::cout << addmax;

	delete[] dp;
	delete[] seqadd;

	return 0;
}

 

• for 문을 2가지 쓰는 순차 진행의 경우 

  ex ) A[0] 부터 시작, A[1] 부터 시작, A[N - 1] 부터 시작

  
  누적값으로 하는 것이 아닌 모든 값을 비교 하기 때문에 많은 시간이 걸린다.

 

결 과 값

 

 

문 제  출 처

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

1912번: 연속합