시나위

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 문제 요약 두 배열이 주어졌을때 각각의 배열로 만들수 있는 부배열의 합이 T가 되는 부배열쌍의 개수 구하기 접근 1. 생각의 흐름 각 배열의 부배열합을 구해서 저장해야한다. 원소가 1개인 것부터 모든 원소가 들어간 것 까지의 부배열을 만들고 그의 합을 저장했는데 누적합을 사용했다. void makeArr( vector& arr, vector& cumArr, int size ) { a..

https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 이차원 배열을 사용한 누적합 문제이다 밝기의 평균을 구할때마다 항상 더하고 나누는 연산을 하는건 꽤 오래 걸린다. 그래서 누적합을 구한다음 특정 범위에서의 합을 구하고 해당 범위의 넓이로 나누면 된다. 일차원 배열에선 누적합을 구할땐 이전 인덱스 값만 계속 더해주면 되는데, 이차원 배열에서 누적합을 구할 땐 행과 열에서 이전 인덱스(memo[i-1]..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분탐색 문제이다. 높이를 오름차순으로 정렬하고 시작점은 0, 끝점은 가장 큰 값(정렬했으므로 마지막 값)으로 설정해서 이분탐색을 한다. 합이 M보다 작거나 같을때는 최솟값을 올리고, 작을때는 최댓값을 내려서 탐색한다. 이때 합도 이분탐색으로 찾는데 처음에 누적합을 구하고, 처음으로 목표값 보다 커지는 인덱스를 찾으면 해당 구간에서의 합을 쉽게 구할수 있다...

https://www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 동적계획법으로 누적합을 사용하는 문제이다. 출석체크 한 사람을 구한뒤에 출석하지 않은 학생을 하나하나 찾아서 계속 시간초과가 걸렸다. 누적합으로 구한뒤에 구간별로 출력하니 통과. import sys; input = sys.stdin.readline # 0 입력 N, K, Q, M = map(int, input().split()) sleep = set(m..