[https://www.acmicpc.net/problem/14846 14846번: 직사각형과 쿼리 첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며 www.acmicpc.net DP와 누적합 문제다. 해당 칸을 기준으로 왼쪽 위쪽으로 존재하는 숫자들의 개수를 세어 배열에 저장한다. 배열은 3차원 배열로 행렬크기에 1~10의 개수를 각각 저장할 수 있는 11의 크기다. 검정색 부분까지의 누적합을 구하기 위해서는 빨간 부분 + 파란 부분 - 보라 부분을 해야한다. 빨간 부분에도 파란 부분에도 보라 부분이 포함되어 있기 때문에 중복 계산되므로 한 번 빼야..
누적합
https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net DP와 누적합 문제다. 불도저가 왼쪽 위에서 오른쪽 아래까지 가는 길에 아래 부분은 사과가 많도록 윗 부분은 바나나가 많도록 지나가야 한다. 불도저는 오른쪽, 아래쪽, 오른쪽 아래 대각선으로 움직일 수 있다. 열을 기준으로 생각을 했다. 아래로 가는 경우에는 아래 칸이 사과인지만 확인해서 빼주면 되고 오른쪽 혹은 대각선으로 움직이는 경우는 그 열에 대해 위의 바나나나 아래 사과만 확인해주면 된다..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투 포인터와 누적 합 문제다. 주어진 배열에서 연속된 수들의 부분합 중에 s이상이 되는 수열 중, 가장 짧은 것의 길이를 구하는 문제다. 투 포인터를 사용하여 앞에서부터 포인터를 옮겨주며 해당 포인터들 사이의 누적 합 연산을 수행했다. 합이 s 미만이면 right 포인터를 한 칸 옮겨주어 합을 늘렸다. right 포인터가 끝에 다달았다면 반복문을 종료했다. (누적 합이 더 커질 수 ..
