BOJ 1121 도형

문제 링크입니다.

다각형이 될 수 있다면

길이가 각각 $a \le b \le c$인 세 선분으로 삼각형을 만들 수 있으려면 $a+b > c$를 만족해야 합니다. 이 부등식은 일반적인 다각형에 대해 성립합니다. 가장 긴 변의 양 끝 점에 닿는 적당한 경로를 나머지 K-1 개의 선분으로 만들 수 있어야 하기 때문입니다.

가장 긴 변 고정하기

주어진 선분을 길이 순으로 오름차순 정렬해 줍니다. 그러면 어떤 선분을 가장 긴 변으로 고정했을 때 그 앞에 있는 선분 중 K-1개를 골라 합을 이번 선분의 길이를 초과하게 만드는 방법의 수를 세는 것으로 문제를 해결할 수 있습니다.

주어진 선분을 순서대로 보면서, 다음의 테이블을 갱신해 줍니다.

• $d[k][l]$ : $k$개의 선분을 골라 길이 합을 $l$로 만드는 경우의 수

이는 배낭 문제의 일종이니 DP로 해결해 줍시다.

각 선분마다, 현재 테이블의 K-1번 행에서 길이 합이 현재 선분의 길이 초과인 것을 전부 답에 더해주고 이번 선분을 포함하도록 테이블을 갱신해주면 문제를 $\mathcal{O} (NK^2 L)$에 해결할 수 있습니다. 선분 길이의 최댓값을 넘어가는 경우를 전부 INF로 처리해주면 $\mathcal{O} (NKL)$로 줄일 수도 있습니다. 실제 실행 시간은 2~3배 정도 빠릅니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int a[55];
ll d[11][505050];

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n;
	d[0][0] = 1;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1, a+n+1);
	int m; cin >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 50000*(m-1); j >= 0; j--){
			if(j <= a[i]) break;
			d[m][501010] += d[m-1][j];
		}
		for(int k = m-2; k >= 0; k--){
			for(int j = 50000*k; j >= 0; j--){
				d[k+1][j+a[i]] += d[k][j];
			}
		}
	}
	cout << d[m][501010];
}