반응형
부분합
-
BOJ) 연속합알고리즘/백준 2020. 6. 12. 23:21
연속합 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 오늘 어려운 문제에 여러개 도전하다가 실패해서 그런지 머리가 잘 돌아가지 않았다. 그래서, 예전에 풀었던 기억이 있어서 참고해서 풀었다. 우선, 막혔던 부분은 partialSum을 저장하는 부분이었다. Math.max(0,partialSum)을 통해 해당 번호에서 다시 시작하는게 좋은지, 지금까지 더해왔던 수를 계속 이용하는게 좋은지 판별해주는 부분이 놓친 부분이었다. 이전까지의 합이 양수면, 거기에 더해주는게 더 합리적이기 때문에.. 또한, 0과 비교하는 이..