본문 바로가기

Algorithm Problems/누적 합

(6)
[백준/C++] 25682번: 체스판 다시 칠하기 2 문제https://www.acmicpc.net/problem/25682문제 요약검은색과 흰색 칸으로 이루어진 M × N 크기의 보드가 주어진다. 주어진 보드판을 K × K 크기로 잘라 체스판을 만들려고 할 때, 필요한 최소 색칠 횟수를 출력한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다.코드#include #include #include #include using namespace std;int n, m, k;char board[2020][2020];// (0, 0)이 B 또는 W인 체스판으로 만들 때, 칠해야 하면 1, 아니면 0int b_board[2020][2020];int w_board[2020][2020];int prefix_b[2020][2020];int prefix_w[2020]..
[백준/C++] 25606번: 장마 문제https://www.acmicpc.net/problem/25606문제 요약장마로 인해 비가 n일 동안 내릴 예정이다. t일 후에 내리는 비가 상자에 물을 채우는 양이 주어진다. 하루 동안 빗물을 받은 상자는 실험실에 보관되는데, 이 때 보관된 상자는 매일 물이 m만큼 증발한다. q개의 질의가 주어질 때, 답을 출력한다. 1 t : 장마 시작 t일 후, 모든 상자에 들어있는 물의 양의 합은 무엇인가?2 t: 장마 시작 t일 후, 모든 상자에서 증발하는 물의 양의 합은 무엇인가?코드#include #include #include using namespace std;int n, m, q;// rain[i][0]: i일까지 내린 비의 양// rain[i][1]: i일까지 증발한 비의 양int rain[10..
[백준/C++] 28420번: 카더가든 문제https://www.acmicpc.net/problem/28420문제 요약너비가 a이고 길이가 b인 차와 너비가 a이고 길이가 c인 캠핑카가 있다. 차와 캠핑카는 3개의 그림 모양으로 n × m 크기의 화전역에 배치할 수 있다. 캠핑카와 차는 회전하거나 뒤집힐 수 없다. 화전역 땅의 단위 구역에는 흐림 정도가 주어진다. 차와 캠핑카가 차지하는 단위 구역의 흐림 정도 합의 최소를 출력한다.코드#include #define MAX 300using namespace std;int n, m, a, b, c;int res = 1e9;int ground[MAX + 1][MAX + 1];int prefix[MAX + 1][MAX + 1];// (x1, y1)부터 (x2, y2)까지의 누적합int prefix_s..
[백준/C++] 10986번: 나머지 합 문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제 요약 N개의 이루어진 수열 A의 연속된 부분 수열의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 코드 ??? 코드 설명 0 ~ i 까지의 누적합 => prefix[i] 부분 수열 (i + 1~ j) 의 합 => prefix[j] - prefix[i] 부분 수열 (i + 1 ~ j) 의 합이 M으로 나뉜다. => (prefix[j]..
[백준/C++] 2042번: 구간 합 구하기 문제 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 요약 N개의 수가 배열 A에 저장되어 있다. 중간에 A[i]의 변경이 빈번히 일어날 때, 어떤 부분의 합을 구하려고 한다. 코드 #include #include #define ll long long #define MAX_N 1000000 using namespace std; ll n, m, k; ll A[MAX_N + 1]; l..
[백준/python] 2167번: 2차원 배열의 합 문제 https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 문제 요약 N × N 크기의 2차원 배열을 입력 받고, 위치 (i, j) 부터 (x, y) 까지 있는 수들의 합을 출력한다. + (i, j), (x, y)는 배열의 i(x)번째 행, j(y)번째 열을 의미한다. (1부터 시작) 코드 import sys input = sys.stdin.readline N, M = map(int, input().rstrip().spl..