알고리즘/문제풀이 - 백준

백준 1912 연속합

문제 : https://www.acmicpc.net/problem/1912 서론 https://hydroponicglass.tistory.com/4 위와 같은 아이디어는 배열이 너무 커서 선언이 되질 않았다. 그래서 이중 for문으로 풀어봤으나 시간초과 결과적으로 DP를 이용한 단일 for문으로 풀어야 하는 문제였다. 풀이 예제 1 2 3 4 5 6 7 8 9 10 10 -4 3 1 5 6 -35 12 21 -1 sum[6]은 1번부터 6번까지의 합인 21이 저장되어있음 sum[6]은 sum[5]보다 큰 수이므로 결과값은 16에서 21로 갱신 sum[7]은 -14로 음수이므로 sum[7]은 0으로 갱신 (음수를 더해줄 시 최대값과 멀어짐) sum[8]은 sum[7]이 0이므로 부분합을 0부터 다시 시작함..

2019. 5. 22. 20:44