[BOJ C++] 13398 연속합 2

https://www.acmicpc.net/problem/13398

13398번: 연속합 2

 

문제 이해

주어지는 배열에서 연속하는 숫자들의 최대 합을 구하는 문제였습니다. 특이한 점은, 그중 한개의 숫자까지는 뺴버려도 된다는 것이였고, 또 주의할 점은 "1개의 숫자는 최소한 선택해야한다" 라는 점이였습니다.(여기서 꽤 틀림)

 

 

입출력 조건

시간초 제한은 2초였으며 최대 배열의 크기는 100,000개 였습니다. 여기서 한개씩 빼면서 탐색을 하게되면 100,000 * 100,000 으로 100억이 넘어가며 시간초과가 날 것이였기에, DP를 써야한다고 짐작할 수 있었습니다.

 

 

풀이

DP를 써야함을 알았지만 시간이 굉장히 오래 걸렸습니다. 식을 찾는데 오래걸렸고 이리저리 쓰다보니 결국 결과에 다다랐습니다.

문제에서 요구하는 i번째까지의 수 중 역속합이 최대가 되는 경우는 다음과 같이 3가지였습니다.

1. i번째 지금 한개의 값이 가장 큰 경우

2. i번째 지금 한개의 값을 빼고 앞선 값을 다 더한 경우

3. 이미 앞에서 한개를 빼고 i번째 값을 포함하며 가장 큰 경우

 

이렇게 설명하니 말이 조금 어려운데,

우선 dp배열을 dp[2][100001] 로 잡았고 dp[0][i]는 아무것도 빼지 않았을 때 i번째 까지 배열의 최대 연속합을 구한 값을 넣고 dp[1][i]는 한개를 뺐을 때 i번째 까지 배열의 최대 연속합을 구하였습니다.

dp[0][i] = max(dp[0][i-1] + now[i], now[i]) 로 생각을 할 수 있었고

dp[1][i]가 문제였습니다.

여기서 이제 저 앞선 3가지가 비교되게 됩니다.

이해하기 힘드실 수 있지만 제가 풀었던 노트입니다..

저렇게 생각하고 한번더 예시를 반복해 보니 확신이 생겼고 이후 코드를 작성하였습니다.

 

 

에러 및 느낀 점

1. 첫번째 놓쳤던 점은 문제에서 얘기한 최소 한개의 값을 가져야 한다는 것입니다. 만약 테스트케이스로 n=1, -1 이 주어졌다면 해당 값을 포함하지 않는 0이 가장 크게 나올 수 있는데 이는 명백히 문제에 반하는 내용이였습니다.

 

2. 최소값을 0으로 잡으면 안되었습니다. 최대값은 1억이구나 하고 int로 되겠네라고 생각하고 말았었는데, 최소값 또한 -1억 까지 갈 수 있어서 더 작은 값을 최초의 최소로 잡아 줄 필요가 있었습니다.

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/13398_%EC%97%B0%EC%86%8D%ED%95%A9%202.cpp

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.