BOJ 1121 - 도형

June 3, 2023

선분을 여러개로 하나의 직선처럼 쓸 수 있는 경우도 고려해야되는줄알고 풀이가 꼬였다.

$K$ 각형을 만들 수 있는 조건은 $K$ 개 의 선분중에서 가장 큰 것을 $K$ 번째라고 할 때,

$\sum_{i=1}^{K-1}L_i > L_K$ 여야 한다는 것이다.

$dp[i][j][k]=i$ 번째까지 선분까지 사용할 수 있고 $j$ 개를 써서 선분 길이의 총합이 $k$ 인 것의 경우의 수라고 한다면

$x$ 번째 선분을 쓰려고 할 때는 $dp[x-1][k-1][L_x+1 \sim \infty]$ 까지의 합을 모두 정답에 더해주면 된다.

물론 선분들의 길이의 합이 $50000$ 을 넘어갈 수 있는데, 이 경우 $50001$ 같은 값으로 처리해두면 된다.

시간복잡도는 $O(NKL)$ 이다.

You may also enjoy