Prefix Sum

[백준] 1644. 소수의 연속합 - 파이썬

[Gold III] https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 1 보자마자, Prefix Sum 문제라고 생각했다. 먼저 에라토스테네스의 체를 이용해 입력값인 N까지의 수 중 소수를 구하고, 그 소수들의 리스트를 이용해 prefix sum 리스트를 만든 후, Two Pointer 기법을 이용해 부분합의 값이 N과 동일한 지 확인하는 방법. 시간은 충분했으나, MLE. (Memory Limit Exceed.) N = int(input()) nums = {i: 0 for i in range(2, N+1)} # 에라토스테네스의 체 for i in nums: ..

[백준] 2143. 두 배열의 합 - 파이썬

[Gold III] https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 부 배열의 합.. -> Prefix Sum! 우선 prefix sum을 구현하기 위해.. Sk (1~k번째 합)를 저장할 배열을 각각 생성. 그 다음이 문제인데... 우선 배열의 원소 조건이 절댓값이 1,000,000을 넘지 않는 정수 이기 때문에.. A[k+1] >= A[k] 가 아니다. 따..

[백준] 1806. 부분합 - 파이썬

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 1 문제 이름과 같이, Prefix Sum (부분합)을 이용하여 풀이하면 되는 문제. 설명은 다른 곳에 더 잘 설명되어 있을 테니 생략. line 13 ~ 16에서 Time Complexity가 O(N^2)이라 TLE. 1부터 N까지의 공차가 1인 등차수열의 합은 n(n+1)/2 이므로.. O(N^2) import sys input = sys.stdin.readline N, S..

[백준] 11659. 구간 합 구하기 4 - 파이썬

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 1 Brute-Force로 풀어봤으나 시간초과 N, M = map(int, input().split()) nums = list(map(int, input().split())) totals = [] for _ in range(M): total = 0 i, j = map(int, input().split()) for k in range(i-1, j): total += nu..