[백준][1912]문제 풀이

문제 형식을 완전탐색형식으로 접근을 해보았지만 배열이 10만을 넘어가는 것을 보고 기존의 방식으로 풀면 안되는 것을 알게 되서 다이나믹 프로그래밍으로 접근을 했습니담..

dp[1]을 처음 준 이유는 n이 1일 수도 있기 때문에 넣어주고 시작을 했어요

처음 포스팅을 했기 때문에 추후에 글 솜씨를 늘려가도록 하겠습니다.

 

 

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {

	int n, ans = 0;
	scanf("%d", &n);

	int arr[100001] = { 0 }; // 데이터 배열 초기화
	int dp[100001] = { 0 }; // dp배열 초기화 

	for (int i = 1; i <= n; i++)
		scanf("%d", &arr[i]);	// 1부터 n까지

	ans = dp[1] = arr[1];	// dp[1] 및 ans에 배열 첫번째 항에 초기화 해주기
	for (int i = 2; i <= n; i++) {
		dp[i] = max(arr[i], dp[i - 1] + arr[i]); // n == 1이 1인 경우도 있으므로 그중에 초기화
		ans = max(ans, dp[i]);					 // 더한 값을 최대값으로 갱신
	}

    printf("%d\n", ans);

}