넘치게 채우기

https://www.acmicpc.net/problem/5625BOJ - 페스트리문제 유형: 누적 합, 스위핑문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제상근 바게트에서 삼각 페스트리 N개를 구웠다. 모든 페스트리는 2차원 평면 위에서 정수 좌표 꼭짓점을 가지는 삼각형으로 나타낼 수 있다.상근이의 말썽꾸러기 아들 정인이는 커다란 칼을 들고 페스트리를 자르려고 한다. 정인이는 좌표평면에서 수직 방향(x = c)이나 수평 방향(y = c)으로 칼질을 한다. 정인이가 칼질을 할 때, 총 몇 개의 페스트리가 잘리는지 구하려고 한다. 페스트리가 칼질로 두 부분으로 나누어졌을 때, 두 부분의 넓이가 0보다 크면 잘린 것이다.페스트리의 위치와 정인이의 칼질이 주어졌을 때, 몇 개의 페스..

https://www.acmicpc.net/problem/1451BOJ - 직사각형으로 나누기문제 유형: 누적합, 브루트 포스, 많은 조건 분기문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제세준이는 N*M크기로 직사각형에 수를 N*M개 써놓았다.세준이는 이 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누려고 한다. 각각의 칸은 단 하나의 작은 직사각형에 포함되어야 하고, 각각의 작은 직사각형은 적어도 하나의 숫자를 포함해야 한다.어떤 작은 직사각형의 합은 그 속에 있는 수의 합이다. 입력으로 주어진 직사각형을 3개의 작은 직사각형으로 나누었을 때, 각각의 작은 직사각형의 합의 곱을 최대로 하는 프로그램을 작성하시오. 입력첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 ..

https://www.acmicpc.net/problem/9527BOJ - 1의 개수 세기문제 유형: 누적합, 수학, 비트마스킹문제 난이도: Gold II시간 제한: 1초메모리 제한: 128MB 문제두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자. ∑x=ABf(x)$$\sum _{x=A}^{B}f(x)$$  입력첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 10^16) 출력1의 개수를 세어 출력한다. 풀이어떤 수 2^i-1에 대한 점화식은 다음과 같다: pows[i]는 (1  i비트의 ..