[백준] 2003번 수들의 합 2 [Python] - 누적 합
N개의 수열과 자연수 M이 주어지면, i번째 수 부터 j번째 수 까지의 합이 M이 되는 경우의 수를 구하는 문제 더보기 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N$(1 ≤ N ≤ 10,000)$, M$(1 ≤ M ≤ 300,000,000)$이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. https://www.acmicpc.net/problem/2003 수열을 ..
[백준] 11660번 구간 합 구하기 5 [Python] - 다이나믹, 누적 합
N×N개의 수가 N×N 크기의 표에 채워져 있다. $(x1, y1)$부터 $(x2, y2)$까지 합을 구하는 문제. $(x, y)$는 x행 y열을 의미한다. 1차원 수열의 구간 합 문제 https://savvy0402.tistory.com/216 위 문제와 비슷하지만 이번에는 2차원 수열의 구간 합을 구하는 문제라고 보면 된다. 더보기 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. $(x1, y1)$부터 $(x2, y2)$까지 합을 구하는 프로그램을 작성하시오. $(x, y)$는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 $(2, 2)$부터 $(3, 4)$까지 합을 구하면 3..