BaekJoon 1912 연속합
2019. 1. 14.
Link https://www.acmicpc.net/problem/1912 소스결과 2652 KB / 8 ms 출처 Backjoon 언어 C++ 17 분류 다이나믹 프로그래밍, 수학 설명 임의의 수열에 대해서 연속된 수의 합이 최대를 구하는 문제 예제만 보고 양수의 합을 구하다가 다음 수가 음수가 나오면 현재 까지의 합을 남기는 알고리즘을 만들었다가 오답 한개를 추가하고 시작했다. 위 예제에서 -35를 21 뒤에 놓는 형태로 바꾸면 문제에 숨겨진 함정이 나온다. 음수가 존재 한다고 해서 그 다음 수를 더했을 때 현재 까지의 합이 최대라는 보장이 없는 함정이 숨어 있다. DP Table 조금 변형을 가해서 현재까지의 합 + 다음 수의 합이 음수가 된다면 음수의 그 다음수가 양수여도 현재 합을 넘을 수 없는..
