[백준][dp] 1912 연속합 c++ 구현

목차

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

1912번: 연속합

 

문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 구현 방향

다이나믹 프로그래밍의 방법 중 하나인 상향식을 이용해 구현하고자 했다.

다이나믹 프로그래밍의 개념을 모른다면 아래 링크를 참고하면 좋다

https://be-senior-developer.tistory.com/19

[DP] 동적 계획법 알고리즘 c++ 설명

 

 

 

문제 풀이

각 수의 다음을 더해줄지 여부에 따라 점화식으로 만들어 주면 된다.

마지막 수부터 누적여부에 따라 값을 넣어주면 된다.

 

예시) 10 -4 3 1 5 6 -35 12 21 -1 

 

• -1다음은 숫자가 없으므로 그냥 넣어준다.

-1

 

 

• 21 + -1 을 한 수보다 21이 더 크므로 21을 넣어준다.

21

-1

 

 

• 12 +21를 한 수가 12보다 더 크므로 33을 넣어준다.

33

21

-1

 

 

• -35 + 33을 한 수가 -35보다 더 크므로 -2를 넣어준다. 

-2

33

21

-1

 

 

• 6 + -2 를 한 수보다 6이 더 크므로 6을 넣어준다.

6

-2

33

21

-1

 

 

• 5 + 6을 한 수가 5보다 더 크므로 11를 넣어준다. 

11

6

-2

33

21

-1

 

 

• 1 + 11를 한 수가 1보다 더 크므로 12를 넣어준다.

12

11

6

-2

33

21

-1

 

 

• 3 + 12을 한 수가 3보다 더 크므로 15를 넣어준다.

15

12

11

6

-2

33

21

-1

 

 

• -4 + 15를 한 수가  -4보다 더 크므로 11를 넣어준다.

11

15

12

11

6

-2

33

21

-1

 

 

• 10 + 11를 한 수가 10보다 더 크므로 21를 넣어준다.

21

11

15

12

11

6

-2

33

21

-1

 

 

이 중 가장 큰 수를 출력해 주면 된다.

 

코드구현

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> narray;
vector<int> sum_array(100000, -1001);   //범위보다 작은 수로 초기화 한다.
int main() {
	int n, num, i, compare;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> num;
		narray.push_back(num);
	}

	for (i = n-1; i >= 0; i--) {
		if (i == n - 1) {  //끝 수이면 그냥 저장
			sum_array[i] = narray[i];
		}
		else {
			compare = sum_array[i + 1] + narray[i];   //더해줄지 말지 여부결정
			if ( compare > narray[i]) {
				sum_array[i] = compare;
			}
			else {
				sum_array[i] = narray[i];
			}
		}
	}

	auto iter = max_element(sum_array.begin(), sum_array.end());
	cout << *iter;
}