BOJ 22348 : 헬기 착륙장

22348번: 헬기 착륙장 (acmicpc.net)

22348번: 헬기 착륙장

dp[i][j] = i개의 동심원, j개의 빨간 페인트를 이용했을 때 만들 수 있는 동심원 갯수

라고 두면 점화식은 이렇다

dp[i][j] += dp[i-1][j-i] (헤당 동심원에 빨간색 원을 만들 때)

dp[i][j] += dp[i-1][j] (헤당 동심원에 파란색 원을 만들 때)

 

이때 우리는 만들 수 있는 모든 헬기 착륙장의 갯수를 만들어야 하므로,

i<=a & j<=b (i는 이용한 빨간 페인트 수, a는 이용할 수 있는 빨간 페인트 수, j는 이용한 파란 페인트 수, b는 이용할 수 있는 파란 페인트 수) 를 만족하는 dp값을 모두 더한게 답이다.

이때 n을 동심원 갯수라고 하면 j = n*(n+1)/2 - i가 되므로

n*(n+1)/2 - b <= i <= a 를 만족한다.

이를 이용해 prefix sum으로 답을 구할 수 있다.

 

코드