Number Partition

$[1,n]$의 수들을 세 더미로 나누는 문제를 조금 더 일반화하여, $[1,m]$의 수들을 합이 $s_1,s_2,s_3$인 세 더미로 나눌 수 있는지 생각하자. 여기서 $s_i$는 $0$일 수도 있다.

$m \geq 3$일 때 불가능한 경우는 다음 두 가지뿐이다.

• $s_i=1$인 더미가 두 개 이상인 경우.
• $s_i=2$인 더미가 두 개 이상인 경우.

합이 $1$인 더미는 반드시 $\{1\}$이어야 하고, 합이 $2$인 더미는 반드시 $\{2\}$이어야 하므로 위 경우는 불가능하다.

구성은 큰 수부터 하나씩 넣는다. 현재 $m,m-1,\cdots,1$을 처리한다고 하자. 아직 남은 목표 합이 $s_1,s_2,s_3$일 때, 을 어떤 더미 에 넣으면 남은 목표 합은 이 된다. 세 더미 중 가능한 모든 선택을 시도해 보고, 남은 에 대해 위의 가능 조건을 만족하는 선택을 고른다.

가능한 상태에서 시작하면 항상 이런 선택이 존재한다. 따라서 $m=n,n-1,\cdots,1$ 순서로 반복하면 실제 분할을 얻을 수 있다.

초기 상태에서 이미 불가능 조건을 만족하면 $\text{NO}$를 출력한다. 그렇지 않으면 위 과정을 통해 얻은 세 더미를 출력한다.

Solution written by GPT5.5