C 구간 합 구하기 41 [C] 11659: 구간 합 구하기 4 그냥 bruteforce하게 이중 for문을 이용해서 푼다면 시간초과가 나온다. 이때 구간 합을 이용하여야 하는데 i번째까지 합을 dp[i]에 저장하였다가 합을 구해야하는 구간에 대해서 result=dp[b]-dp[a-1]; 를 통해 구하면 된다. DP라고 보기에는 애매할 수도 있으나 중복되는 부분 문제를 줄일 수 있다는 점에서 의의가 있는 것 같다. 이건 꼭 알아야한다! 구간 합을 이용하면 시간복잡도를 n^2에서 n으로 획기적으로 줄일 수 있다! #include int arr[100001]; int dp[100001]; int main(void) { int n,m; scanf("%d %d",&n,&m); for(int i=1;i 2023. 8. 21. 이전 1 다음