kanght1219   2년 전

Dp[i][j] = (길이가 i 이고 혼란도가 j인 수열의 갯수)

Pf[i][j] = (길이가 i 이고 혼란도가 j 이하인 수열의 갯수)라고 정의해서

Dp[i][j] = Pf[i - 1][j] - Pf[i - 1][j - i]

Pf[i][j] = Dp[i][j] + Pf[i][j - 1]

로 정의해서 Dp[i][j]를 구하다가 틀려서 Pf 배열과 Dp 배열을 유심히 보다 Pf 배열에서 답을 내서 Pf 배열에서 출력하니 맞았습니다.

왜 DP 배열이 아니라 PF 배열에서 답이 나오는 건가요?

댓글을 작성하려면 로그인해야 합니다.