연속합2 [Swift][DP] 백준 13398번 (연속합 2) 요구능력 : DP에 대한 이해 코드설명 : 이 문제는 연속합 문제를 선행학습 하고 오셔야 이해가됩니다. 문제의 핵심 1. 연속합 2. 수를 하나 제거할 수 있다. 3. 수를 제거하지 않을 수도있다. 이 문제는 연속합이기 때문에 연속적으로 합을 구해줘야 하는데 수를 하나 뺄수 있다. 중요한점은 꼭 왼쪽에서 부터 시작한다는 생각을 버려야 한다. 만약에 -35라는 수를 빼고 연속합을 구하고싶다면 -35를 기준으로 가장 왼쪽에있는값 10부터 6까지의 연속합과 가장오른쪽에 있는값 -1부터 12까지의 연속합을 구해주면 된다. 이렇게 하면 왼쪽부터 -35만빼고 연속합을 모두 고려할수 있는것이다. 10 -4 3 1 5 6 -35 12 21 -1 n = 정수를 입력받는 부분 arr = n개의 정수로 이루어진 수열 dp_.. 2021. 11. 22. [Swift][DP] 백준 1912번 (연속합) 요구능력 : DP에 대한 이해 코드설명 : 이 문제에서 만들어 놓은 함정에 빠지고 문제를 풀 수 없었다.. 함정은 바로 음수를 빼는 조건을 거는것이다. 음수포함해서도 연속값이 큰값이 나올 수 있다. 만약 음수를 빼는 조건을 거셨다면, 2번째 예제에서 14가 안나올것이다. 일단, 이 문제는 문제이름대로 dp에 연속적으로 합을 누적시킨다고 생각하면 된다. dp[0] = arr[0] 을 해준 이유는 dp[0]에는 arr[0]만 누적된거다. dp[1] = max(arr[1], dp[0] + arr[1]) dp[2] = max(arr[2], dp[1] + arr[2]) . . 이런식으로 값을 계속해서 누적 시킨다. max를 쓰는 이유는 값의 누적이 쓸모없어졌을 순간, 바로 현재 값이 이전에 (누적된 값 + 현재값.. 2021. 10. 5. 이전 1 다음