백준11660

[백준 11660] 구간 합 구하기 5 C++

www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 다이나믹 프로그래밍 알고리즘을 사용해서 푸는 문제입니다. map의 전체 사이즈는 최대 1024x1024이고, 연산을 최대 100,000번 해야하기 때문에, 브루트포스로 풀게되면 당연히 시간초과가 나올 수 밖에 없습니다. 시간초과가 나오지 않으려면, DP를 사용해서 각 인덱스별로 누적합을 저장하면 되겠습니다. dp[i][j]는 i, j까지 누적합을 말합니다. 입력을 받을..