[C언어] 백준 1912 : 연속합
생각의 흐름
처음엔 그냥 마이너스있으면 다 0으로 초기화시키면서 sum에 저장하며 max를 찾아주면 되겠구나 싶었다. 뭐 굳이 dp 써야되나? 싶었다 이게 dp인가? 모르겠다.
그래서 일단 양수의 합만 체크하는걸로 코드를 작성했다.
예제1에 12와 21을 더한 최댓값 33은 잘 나왔지만, 예제2에서 최댓값이 11이 나왔다. 이유는 3 + 4 - 4 + 6 + 5 로 마이너스가 있어도 계산을 해주어야 한다.
아 그러면 내가 위에 적은 값과 비교해서 max값인걸로 출력하면 끝나겠구나 생각했다.
예제2를 어떤식으로 생각했냐면, 똑같이 sum에다 숫자를 하나씩 더해주면서 진행한다. 바로바로 max체크를 해주면서 진행한다. 그러다가 sum이 음수가 되는경우, 앞에있는 연산은 다 버린다. 왜냐하면 앞에있는걸 챙겨가면 무조건 손해를 보기 때문이다.
그렇게 음수가 나오면 0으로 초기화하고, 진행하며 max를 찾아준다.
맨 위에서 정한 max값과 방금정한 max1값을 비교해서 최댓값을 출력하면 끝이다.
내가 푼 코드
#include <stdio.h>
#define MAX(a, b) (a > b ? a : b)
int main()
{
int i, n;
int arr[100001];
int sum = 0, max = -1001;
int result;
scanf("%d", &n);
i = 0;
while (i < n)
{
scanf("%d", &arr[i]);
i++;
}
i = 0;
while (i < n)
{
if (arr[i] > 0)
{
sum = sum + arr[i];
if (max < sum)
{
max = sum;
}
}
else if (arr[i] < 0)
{
sum = 0;
}
i++;
}
i = 0;
sum = 0;
int max1 = -1001;
while (i < n)
{
sum = sum + arr[i];
if (max1 < sum)
{
max1 = sum;
}
if (sum < 0)
{
sum = 0;
}
i++;
}
result = MAX(max, max1);
printf("%d", result);
}
Author And Source
이 문제에 관하여([C언어] 백준 1912 : 연속합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmainsain/C언어-백준-1912-연속합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)