문제 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103) 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) 출력 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 풀이 부분 합을 계속 구했더니 시간 초과가 발생하였고, 결국 ChatGPT 도움을 받아서 해결했다. 그런데 봐도 봐도 이해가 잘 안돼서.. 결국 이해 했지만, 나와 같은 사람이..
문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N 시간초과 import sys input = sys.stdin.readline n, s = map(i..
누적합(cumulative sum)은 배열의 각 원소까지의 합을 미리 계산하여 누적한 값을 저장한 배열입니다. 이를 이용하면, 구간 합을 빠르게 계산할 수 있습니다. 구간 합은 배열에서 주어진 구간에 속한 모든 원소의 합을 의미합니다. 예를 들어, 배열 arr에서 2번째 원소부터 5번째 원소까지의 합을 계산해야 한다면, 다음과 같이 코드를 작성할 수 있습니다. arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] start = 2 end = 5 sum = 0 for i in range(start, end+1): sum += arr[i] print(sum) 위 코드는 구간 합을 계산하는 가장 간단한 방법입니다. 하지만, 배열의 크기가 크고 구간 합을 계산해야 하는 횟수가 많아질 경우에는 이 ..
