BOJ 18317 - Farmer John Solves 3SUM

BOJ 18317 - Farmer John Solves 3SUM

$dp[l][r]=[l,r]$ 구간에서 $a[i]+a[j]+a[k]=0$ 이 되는 경우의 수라고 하자.

$dp[l][r]=dp[l+1][r] + dp[l][r-1] - dp[l+1][r-1]$ 이다.

포함 배제의 원리?

나는 이 수식으로 안풀고 $dp[l][r]=dp[l][r-1] + c[l][r]$ 로 풀었다.

$c[l][r]$ 이란 $l \sim r-1$ 구간에서 $-a[r]$인 $a[i]+a[j]$의 개수이다.

사실 두 식은 전단사적으로 같으므로 $c[l][r]=dp[l+1][r]-dp[l+1][r-1]$ 임을 알 수 있다.

어떤 방식으로 풀어도 $O(N^2)$이 가능하고 쿼리는 개당 $O(1)$에 처리해줄 수 있다.

iPad에 PS IDE 환경을 구축했는데 cin untie를 안해줘서 계속 시간초과가 났다.