주어진 배열을 원소들의 합이 같은 두개의 하위집합으로 분할가능한가?

조건: 배열의 원소들이 양수인 경우

 

구하는 단계

1. 배열의 원소들의 합을 계산한다.

2. 합계가 홀수라면-> 합이 같은 두개의 하위집합이 있을 수 없다.

                 짝수라면-> sum/2를 계산하고 합이 sum/2인 배열의 하위 집합을 찾는다.

 

dp를 사용하여 해결하기

 

1. 원소들의 합이 짝수인지 확인

2. (sum/2) + 1 * (N+1) 크기의 2차원 배열 part[ ][ ] 선언  // N은 주어진 배열의 원소 개수

3. part[i][j] 에서 i는 원소들의 합, j는 합 i를 만들 수 있는 원소들의 개수

4. part[i][j]의 경계 조건 :

part[0][i]는 합이 0이 되는 경우 -> 빈 배열이면 가능하므로 true로 설정 (i는 0이상 n이하)

part[i][0]은 합이 i가되는 원소의 개수가 0인 경우 -> 불가능하므로 0으로 설정 ( i는 1이상 sum/2 이하)

5.

part[i][j] 채우는 원리 

 

세로줄에는 각각 원소들, 가로줄에는 0부터 sum/2까지가 배치되어 있다고 해 보자. 

 

2, 3, 7, 8, 10을 0개씩 쓰면 합이 0이 될 수 있으므로 첫 줄을 다 T로 채워준다. 

 

1은 2의 합으로 될 수 없으므로 F. 

 

2는 2의 합으로 될 수 있으므로 T. 

 

3 이상의 값은 2로 만들어질 수 없으므로 전부다 F. 

 

3보다 작은 값은 !!!윗줄을 그대로 채워준다

 

 

 

3은 T

 

이제 4부터가 중요한데,

일단 바로 윗줄이 true이면 true를 써준다. 

만약 false라면, 

T[윗줄][4-rowValue]을 봐서, true이면 true를 써준다. 

그것도 아니라면 false가 된다. 

 

4는 윗줄도 false, T[0][1]도 false여서 false. 

 

 

5는 윗줄은 false이지만 T[0][2]가 true여서 true. 

 

나머지는 false. 

 

남은 칸들도 위와 같은 방식으로 채워준다. 

 

 

for( int i=1;i<=sum/2;i++){
    for(int j=1;j<=N;j++){
        part[i][j]=part[i][j-1];  // 원소의 개수가 하나 적은 경우와 일단 같은걸로 설정
        if(i>=arr[j-1]){  // 합 i가 주어진 배열의 전 인덱스 값보다 크거나 같다면
              part[i][j] = part[i][j]
                             || part[i - arr[j - 1]][j - 1];
        
    }
}