목록누적합 (3)

1일1알

백준 16507번 어두운 건 무서워 C++

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 누적합 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; in..
알고리즘 2023. 6. 22. 13:28
백준 15724번 주지수 C++

https://www.acmicpc.net/problem/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 누적합 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, m; vector rowSum; int mai..
알고리즘 2022. 10. 24. 16:10
백준 2143번 두 배열의 합 C++

우선 A와 B의 모든 구간에서의 누적합들을 저장하는 벡터를 만든다. A의 누적합과 B의 누적합을 더했을때 t가 되는 경우를 찾으면 되는데, 이분 탐색을 위해 둘중 하나를 정렬한다. 나는 B를 정렬했다. A의 모든 원소를 탐색하면서 B의 원소의 값이 t - A[i]인 경우를 찾으면 되는데, 이때 lower_bound와 upper_bound를 사용했다. lower_bound와 upper_bound는 이분 탐색을 해주는 함수인데, 정렬이 되어있어야 사용이 가능하다. 그래서 앞에서 B를 정렬했다. lower_bound는 찾고싶은 수보다 같거나 큰 인덱스를 반환하고 upper_bound는 찾고싶은 수보다 큰 인덱스를 반환한다. ans에 (upper_bound의 반환값 - lower_bound의 반환값) 을 더해주..
알고리즘 2022. 7. 20. 11:29
이전 Prev 1 Next 다음