[platinum4][해설안봄 dp분류 참조] 국회

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

 

 

문제는 단순해 보이지만 dp 구현방향은 참신했고, 특히 의회의 종류의 자취를 찾아가는 과정과 무엇보다 메모리 이슈가 힘든 문제였다.

연합에서 당 하나만 빠져도 절반 이하가 되어야 하는데, 여기서 의석의 수가 최솟값인 당이 빠져도 절반 이하가 된다면, 어떤 당을 빼도 절반 이하가 될 것이다.

그냥 dp[의석의 수][당중의 의석의 최솟값]으로 순회하면서 dp를 구할 수 있지만 그렇게 된다면 시간복잡도는 O(N * N * 100000)이 될 것이므로 비효율적일것이다.

 

최적화를 위해서 의석의 수의 내림차순으로 의회를  정렬해본다.

 

 

council[i]

1 3 2 4 -> 4 3 2 1

오른쪽으로 순회할 때. i번째 의회를 연합으로 선택하게 된다면 연합에서 좌석의 최솟값인 의회는 i번째가 될 것이다. 

따라서 i번째를 선택했을 때, i번째를 "빼도 의석의 수가 절반이하가 된다면 깔끔한 연합이 될 것이다.

 

 

이렇게 구하기 위해 dp[의석의 수] 만 있으면 의석의 합이 최대인 깔끔한 연합을 구할 수 있다.

시간복잡도도 i번 순회하면서 의석의 수를 순회하므로 O(100000 * N ) 이 될 것이다.

 i를 돌며 순회하다가 dp[의석의 합계 + council[i] ]  이 (전체의석수의 절반 + council[i])보다 작다면 될것이고, 이중에 의석의 합계 + council[i] 가 최대일 때를 구하면 된다.

 

이제 정답을 구하게 된 자취를 되돌아 가는 과정을 거쳐야 한다.

처음엔

 

trace[의석의총합][0] = 이전 의석의 이름,

 trace[의석의총합][1] = 이전의 의석의 총합 

 

로 의석의 수가 최대인 값이 답이므로, 

가능한 깔끔한 연합의 좌석의 총합을 max라 하면

trace[max][0] 로 자취를 구해보려고 했다. 

그러나 i번째  일때 trace[max][0] trace[max][1] 에 값을 넣고 i를 넘어 순회할 때 의석의 수가 max 가 된다면, 이때 trace[max]에 업데이트를 하게되므로 잘못된 값이 나오게 된다.

따라서 visited[] 배열을 도입해 이미 trace를 구한 총합값은 더이상 trace를 업데이트 하지 않게 하면 된다.

간단하지만 이 부분때매 고생을 꽤 했다..

 

또한 메모리 문제는 다음과 같은 난항을 겪었다.

 

1.처음에 visited 함수 없이 진행할 때 , 총합 list에 새로 구한 총합을 계속 더하니 중복된 값이 더해져 당연히 메모리 초과

 

2. Set<Integer> totalSet 로 중복없이 구하려 할때  i번째에서 새로 구한 총합들을 innerSet<Integer>로 구해서 totalSet에 더하는 방식으로 하려 했으나... innerSet을 반복해서 초기화할 때 GC가 메모리를 빠르게 회수를 못해서 그런건진 모르겠지만 메모리 초과

 

3.List<Integer>로 바꾸고 visited함수를 도입해 중복되는 값은 피하고, 향상된 for문으로 순회하면 modification error가 발생해 일반 index로 구하는 for문으로 구하며 총합값들을 add. add는 마지막 인덱스로 가기 때문에 중복문제가 발생하지 않는다.

 

간단한 문제지만 낯선 이슈였다... 부디 다음엔 이런 실수를 하지 않기를