partial sum 검색 결과

해당 글 5건

[백준 16507] 어두운 건 무서워

문제 : https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사진 정보가 주어지며, 사진의 각 픽셀에는 밝기를 의미하는 정수 K (1 ≤ K ≤ 1,000)가 주어진다. 다음 Q개의 각 줄에는 사진의 일부분을 나타내기 위한 두 꼭짓점을 의미하는 정수 r1, c1, r2, c2 (1 ≤ r1 www.acmicpc.net 2차원 배열 형태로의 부분 합 문제이다. 부분 합을 구할 때와 범위 합을 리턴할 때 계산을 주의하면 된다. 또한 평..
PS/백준 문제풀이 2019. 8. 8. 10:41

[백준 10986] 나머지 합

문제 : https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. www.acmicpc.net 알고스팟의 크리스마스 선물 1번과 동일한 문제이다. (https://algospot.com/judge/problem/read/CHRISTMAS) (psum[e] - psum[s-1]) mod M = 0 psum[e] mod M == psum[s-1] mod M 위의 성질을 이용해서 푼다. count에 들어있는 나머..
PS/백준 문제풀이 2019. 8. 8. 10:15

[백준 16139] 인간-컴퓨터 상호작용

문제 : https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 줄부터 $(q+2)$번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 $\alpha_i$와 $0\leq l_i\leq r_i> str; for(int i = 0; i < 26; i++) psum[i].resize(str.size()); for(int i = 0 ; i < str.size(); i++){ int letter = str[i] - 'a'; // 알파벳..
PS/백준 문제풀이 2019. 8. 7. 22:22

[백준 11659] 구간 합 구하기 4

문제 : https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. www.acmicpc.net 2019/08/07 - [PS/Tip] - [C++/STL] 부분 합 partial_sum( ) [C++/STL] 부분 합 partial_sum( ) 특정 구간의 합을 O(1)에 구하고 싶을 때, 부분 합(partial sum)을 미리 구해놓으면 가능하다. 부분 합은 다음과 같다. i 0 ..
PS/백준 문제풀이 2019. 8. 7. 18:17

[C++/STL] 부분 합 partial_sum( )

특정 구간의 합을 O(1)에 구하고 싶을 때, 부분 합(partial sum)을 미리 구해놓으면 가능하다. 부분 합은 다음과 같다. i 0 1 2 3 4 v 1 2 3 4 5 psum 1 3 6 10 15 자 이제 여기서 특정 구간의 합만 구하는 방법은..? 원하는 구간 [a-b] (psum[-1] = 0 이라고 가정) psum[b] - psum[a-1] 부분합은 for 문을 사용해서 O(n)의 시간으로 직접 구할 수도 있고 c++ 의 경우에는 STL을 사용할 수 있다. #include #include // for copy #include // for multiplies #include // for partial_sum #include // for vector using namespace std; int..
PS/Tip 2019. 8. 7. 09:34