문제 링크
- http://icpc.me/2453
문제 출처
- 2011 KOI 고등부 2번
사용 알고리즘
- DP
풀이
각 사람들 사이의 관계는 그래프로 나타낼 수 있습니다. 그래프를 순회하면서 각 그룹의 사람 수를 구해줄 수 있습니다.
각 그룹의 사람들을 두 개의 부서에 적절하게 나눠서 배치해 차이를 최소화해야 하는데, DP로 구해줄 수 있습니다.
dp[n][k] = n번째 그룹까지 고려했을 때 (부서1 - 부서2) = K로 할 수 있는지 여부 처럼 정의를 해주면 쉽게 구할 수 있습니다.
K가 음수가 될 수 있으니 10000정도 더해주면 모두 자연수 범위에서 처리할 수 있습니다.
MLE가 뜰 수 있기 때문에 적절히 토글링을 해주면 됩니다.
전체 코드
1 |
|