UVa 562. Dividing coins. AC get -_-;

<SPAN id=tx_marker_caret></SPAN>#include <iostream> using namespace std; #define max 50002 int coinVal[101], coinNum, sum; int pos[max]; int main() { int n, i, half, j, k; cin >> n; while (n--) { sum = 0; cin >> coinNum; for(i = 0; i < coinNum; i++) { cin >> coinVal[i]; sum += coinVal[i]; } half = sum / 2; pos[0] = 1; for(j = 0; j < coinNum; j++) { if(coinVal[j] > half) { continue; } for(k = half - coinVal[j]; k >= 0; k--) { if(pos[k]) { pos[k + coinVal[j]] = 1; } } if(pos[half]) { break; } } for(j = half; j >= 0; j--) { if(pos[j]) { break; } } k = (sum - j); k = k - j; cout << k << endl; if(n) { for(i = 1; i <= half; i++) { pos[i] = 0; } } } return 0; }<SPAN id=tx_marker_caret></SPAN>

하앍하앍.

원래 리스트와 셋을 이용해 처리하려 했습니다만,

이 빌어먹을 UVa는 .end()로 얻는 포인터에서 --연산으로 뒤에서부터 하나씩 전진해오면 RE가 뜨는군요.

이 풀이는 단순합니다.

일단 여기선 귀찮아서 int형으로 해뒀는데,

pos배열처럼 bool형으로 된 크기 n(동전 가치 총합)의 배열을 만듭니다.

이후, 각 동전 가치 부분은 당연히 2명이 나눠가질 수 있는 분할을 만들 수 있고

거기에 두세개 이상의 동전을 합했을때 나눠지는 경우까지 모두 이 pos 배열에 저장해서

그 분할되는 지점만을 true로 둡니다.

이후, half(정 중앙 지점)에서부터 양쪽 어디든지 가장 가까운 true를 찾아내어서

그 때의 두 수의 차이를 출력하면 문제는 해결됩니다.