안녕하세요,
재재입니다.
BOJ 4384 공평하게 팀 나누기에 대한 솔루션입니다.
BOJ 4384 공평하게 팀 나누기
(1) 문제 설명
분류 : dynamic programming
출처 : https://www.acmicpc.net/problem/4384
(100명 이하) N 명의 학생의 점수가 주어집니다.
각 점수는 450이하입니다.
학생을 두 그룹으로 나누고,
나뉘어진 두 그룹 내의 숫자는 기껏해야 1명의 차이여야 합니다.
이때, 두 그룹의 점수의 차이를 최소로 해야합니다.
(2) 풀이 도출
해당 점수를 만드는게 가능한지를 판단하면 되는 형태의 문제입니다.
따라서, 상태공간을 바로 잡을 수 있습니다.
dp[i][j] : i명 선택했을 때, 점수의 합이 j 인 경우 최적
두 그룹의 숫자는 1명을 초과할 수 없기 때문에,
최대 50명까지 선택이 가능하며 결국 공간복잡도는,
다음과 같이 요구됩니다.
$$ [N/2][450(N/2)] = 50(450*50) $$
(3) 정답 코드
BOJ 4384 공평하게 팀 나누기