[백준] 4384번: 공평하게 팀 나누기 -JAVA
문제 바로 가기 > 4384번: 공평하게 팀 나누기0/1 냅색 알고리즘으로, DP로 풀 수 있다.이 문제는 '부분집합의 합' 문제의 변형으로 볼 수 있다. 우리의 목표는 전체 무게의 절반에 가장 가까운 부분집합을 찾는 것이다.2차원 boolean 배열 dp를 사용합니다.dp[i][j]는 i명의 사람을 선택하여 정확히 j 무게를 만들 수 있는지 여부를 나타낸다 (true/false)알고리즘1. dp 배열 초기화: dp[0][0] = true (0명으로 0kg을 만들 수 있음)2. 각 참가자에 대해:1명부터 전체 인원의 절반까지 선택하는 경우를 고려가능한 모든 무게 조합을 계산하여 dp 배열 갱신for(int i=0; i0; j--){ for(int k=totalWeight; k>=weights..
