[백준 1912번] 연속합

BOJ 1912번 연속합

https://acmicpc.net/problem/1912

백준 1912번 C++ 소스

코드설명 

long long으로 한 이유는 예를 들어 N이 100000까지 입력이 들어올텐데 만약 100000개가 모두 1000이

입력되었다고 가정하면 더하는 과정에서  DP랑 val변수에 오버플로우가 발생할 수 있기 때문이다.

arr는 int형으로 하려다가  max()  함수의 특성상  long long과 int가 

 서로 자료형이 달라서 그런지 아래사진처럼  max함수 수행이 안되어서 그냥 arr도 DP자료형이랑 똑같이 

 long long으로 선언했다.

이 문제는 DP(동적계획법)로  풀어야한다. 

DP[i] = max(DP[i - 1] + arr[i], DP[i]);   

DP[i] = max(DP[i - 1] + arr[i], arr[i]);   

이 2개 점화식을 테스트케이스에 대입하면서 엄청 고민했었다. 

먼저 DP[i] = max(DP[i - 1] + arr[i], DP[i]); 를 하게되면,

4

1 2 -6 250 

위의 테스트 케이스 일때, 

정답은 맨 끝자리수 1개만 250이 나와야 하는데,

 1+2-6 까지 연산한 후에 +250을 하기 때문에 오답이 발생하게 된다.

그래서 

DP[i] = max(DP[i - 1] + arr[i], arr[i]);    으로 바꾸고,

4

1 2 -6 250 

위의 테스트 케이스 일때, 

250을 잘 뽑아냄.

---

val변수를  생각하게 된 계기.

4

1 2 -6 -100

위의 테스트 케이스 일때 DP[i] = max(DP[i - 1] + arr[i], arr[i]); 

이 점화식만으론 또 해결이 안되었다.   

DP[2]부터 -3이 나오기 때문에 이걸 방지하기 위해 val변수에

DP[1]을 저장해두고 와야한다.   

val변수에 미리 3을 저장해두면 그 뒤에 아무리 음수가 나와도 val값은 변하지 않을 것.

10

10 -4 3 1 5 6 -35 12 21 -1 

위의 테스트 케이스일 때도 val변수가 없을때  미리 12+21=33을  저장해두지 않을 경우 

뒤에 -1을 대비하지 못하게됨. 

val변수에 33을 저장해두어 DP[9] 에 32가 저장이 되어도, DP[9]를 무시하고 

DP[8]에 해당하는  33을 출력할 수 있게됨. 

따라서 val = max(val, DP[i]);  코드가 필요하게 된다.

---

val = DP[0];

1

-100 

위의 테스트 케이스처럼 N이 1일때 필요함.  저 코드가 없으면 그대로 -992299를 출력하게되서 

N이 1일때 오답이된다.

---

소스코드

#include "pch.h"
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

int main(void)
{
	long long DP[100001], val=-992299, arr[100001];
	int i, N;

	cin >> N;

	for (i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	DP[0] = arr[0];
    val = DP[0];

	for (i = 1; i < N; i++)
	{
		DP[i] = max(DP[i - 1] + arr[i], arr[i]);
		val = max(val, DP[i]);
	}

	cout << val << endl;
	
	return 0;
}

개발환경 및  컴파일 기준은 visual studio community 2017