BOJ 18858 - 훈련소로 가는 날

image.png

구간합 배열을 잘 쓰면 O(NM)O(NM) 에도 풀 수 있다.

단순하게는 O(NM2)O(NM^2) 으로 푸는 방법이고, 두 방법은 다르지 않다.

dp[i][j][big]dp[i][j][big] 를 ii번째 수까지 이전 수가 jj이고 전전수보다 이전수가 큰지 여부가 bigbig일 때 경우의 수로 두면 된다.

image.png

1등잼

Tags:

Categories:

Updated:

Comments

You may also enjoy