와아 역대급 과제 하나 끝냈습니다.

알고리즘 수업 과제인데 으으 너무 어려웠네요. 근데 어제 새벽에 겨우 끝냈습니다. 성공하니까 희열이 장난아닙니다.(역시 이맛에 과제하지ㅎㅎ)

과제내용

n개의 서로 다른 양의 정수가 주어져 있음
각각의 집합의 합이 같도록 두개로 쪼갬
예를 들어 1,2,3이 있으면 1,2랑 3으로 쪼갬

두개의 집합으로 파티셔닝할 수 있는 경우의 수 출력
그리고 파티셔닝한 거 아무거나 한 개 출력

없으면 0 출력

예를 들어 입력이 {1,2,3,4,5,6,7}이면

경우의 수는

 {1,6,7}, {2,3,4,5}
 {2,5,7}, {1,3,4,6}
 {3,4,7}, {1,2,5,6}
 {1,2,4,7}, {3,5,6}
로 총 4개

정수의 개수는 1 <= n <= 1000

정수의 크기는 1 <= n <= 1500

처음엔 어떤 부분집합의 합이 전체의 절반이면 나머지 원소의 합도 전체의 절반이 된다는 점에서

재귀함수를 이용해 모든 부분집합을 구하고 그 합이 전체의 절반이 되는지 카운트하는 방식으로 만들었는데

시간복잡도가 2^n이라 숫자가 30개만 되도 30초나 걸리고 속도가 느려터졌더라고요.

결국 처음부터 다시 짜는데 교수님이 동적계획법을 사용하라는 힌트를 주셨어서 어제 하루종일 공부한 끝에 성공했습니다.

대신 램은 2GB나 먹는게 함정..ㅎㄷㄷ

짜잔~ 2초이내로 계산이 끝납니다.

어 근데 이제 과제가 몇 개 남았지

팀플 하나, (이것도 역대급 난이도) 과제 하나..., 이번 주에 팀플 하나 더 추가될 예정이고, 다음 주에 과제 2개 추가예정...

우웨에엑ㅠㅜ