문제 링크 http://icpc.me/23247 23247번: Ten A real estate company IC is managing a rectangular section of land. The section is divided into $mn$ segments in $m \times n$ matrix shape, where the number of rows and that of columns are $m$ and $n$, respectively. Each segment has its own price as a posi www.acmicpc.net 풀이 2차원 누적합을 이용하는 문제다. 2차원 누적합을 모른다면 2차원 누적합 설명을 참고해라. 모든 경우를 확인하며 넓이가 300이 되는 경우를 찾으면 ..

문제 링크 http://icpc.me/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 풀이 2차원 누적합으로 풀 수 있다. 누적합을 이용하지 않고 푼다면 주어진 쿼리를 모두 확인하는 방식으로 푼다면 O(RCQ)로 10억이 넘어가 시간이 터질 것이다. 그렇기 때문에 누적합을 이용하여 쿼리당 O(1)에 구간 합을 구해야 한다. psum [i][j] : 오른쪽 아래 꼭짓점이 (i, j)에 있을 때 내부에 있는 밝기의 합이라고 할 때, psum [i][j]는 ..

문제 링크 http://icpc.me/2015 풀이 누적합을 이용하여 풀 수 있다. 0~i번째까지의 합을 미리 구해놓고, 구해놓은 누적합을 잘 관찰하여 풀 수 있다. psum[i] : 0 ~ i까지의 합이라고 할 때, i ~ j까지의 합은 psum[i] - psum[j-1]이다. 이때 구간 합이 k가 되는지 확인할 수 있는 여부는, psum[i] - psum[j-1] (j < i) == k가 되는 j 값이 몇개 존재하는지 확인하면 된다. 그리고 psum[i] 자체가 k인지도 체크하면 된다. 그렇기 때문에 psum[1] ~ psum[n]까지 값을 기록해야 하는데 값의 범위가 20억으로 매우 크므로 그냥 배열을 만들 수 없어, map을 이용하여 저장한다. 코드 #include #include #include..