백준 BOJ 1912 - 연속합

무난한 dp 문제였다

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

1912번: 연속합

 

dp문제를 쬐끔 풀어보면서 느낀게 있다면,

입력배열에서 모든걸 처리하려면 골치아프다는것이다.

그냥 dp배열 하나 더 만들자 ㅎㅎ

 

#include <stdio.h>

int input[100001] = {0};
int dp[100001] = {0};

int max(int a, int b){ return a>b?a:b; }

int main(){
	int n,value = -1234;
	
	scanf("%d", &n);
	for(int i=0; i<n; i++) scanf("%d", &input[i]);
	
	dp[0] = input[0];
	for(int i=0; i<n; i++){
		dp[i+1] = max(dp[i]+input[i+1], input[i+1]);
	}
	
	for(int i=0; i<n; i++) value = max(value, dp[i]);
	printf("%d", value);
	return 0;
}

dp[k]를 index[k] 숫자를 선택할때의 최대값으로 정했다.

아무것도 선택하지 않을수는 없으므로 dp[0]은 input[0]이기에 먼저 한줄 써줬고,

dp[i+1]는 i+1이라는 숫자를 선택했을 때이다.

이때 ( i를 선택했을때의 최대값 )인 dp[i] 의 값이 만약 양수라면 선택해주는게 최대값을 만들어낼 수 있을 것이고,

음수라면 그냥 input[i+1]만 선택해주는게 좋다.

그래서 둘중 큰 수를 반환하는 max함수를 간단히 작성해서 비교해주었다.

​

for문 한번 돌려서 최대값을 value변수에 담아주고,

출력만 하면 AC.

​