전체 글 썸네일형 리스트형 BOJ)2775 부녀회장이 될테야 문제: icpc.me/2775 a층 b호에 사는 주민은 a-1층의 1~b호까지의 주민의 합일때 k층n호에 사는 주민의 수를 출력하는 문제이다. 사실 k와 n의 범위가 매우 작기 때문에 그때 그때 구해줘도 TLE를 받을일은 없을것 같지만 우리는 배운 사람들이니까 다이나믹 프로그래밍을 통하여 쉽게 답을 구 할수 있다. 점화식은 dp[i][j]=dp[i-1][j]+dp[i][j-1] 이다. 12345678910111213141516171819#include #include using namespace std;int dp[15][15], t, k, n;int main() { for (int i = 1; i 더보기 BOJ)5480 전함 문제: icpc.me/5480 각 레이저가 파괴하는 전함의 무게의 최댓값을 출력하는 문제이다. 우리는 우선 쿼리를 전부 받아 오프라인으로 문제를 풀어볼거다. 일단 x좌표와 y좌표가 10억까지들어올수 있기 때문에 전함과 레이저의 x,y좌표를 모두 받아 각각 좌표압축 해준다. 이후 우리는 x와 y에 대한 세그먼트트리를 각각 생성하여 세그먼트 트리에 레이저의 인덱스의 최솟값을 저장할 것이다. 수직인 레이저는 x세그먼트 트리에 수평인 레이저는 y세그먼트 트리에 레이저의 인덱스를 해당 좌표에 최솟값 업데이트 시켜주면 된다. 이후 전함마다 각각 x,y세그트리에서 최솟값인 인덱스를 받는다 가장 작은 인덱스가 의미하는건 결국 그 전함을 파괴하는 레이저라고 보면 된다. 해당 레이저에 전함의 무게를 최댓값으로 업데이트 시.. 더보기 BOJ)10167 금광 문제: icpc.me/10167 직사각형 모양의 영역으로 금광을 개발 할 때 얻을 수 있는 최대 이익을 구하는 문제이다. 문제를 푸는데 상당히 고생했는데 KOI 2014 중등부 문제인걸 보고 어이가없어서 웃음만 나왔다... 일단 N이 3000이므로 N^2혹은 N^2logN 알고리즘을 사용해야 하는데 처음 생각한것은 x축기준으로 스위핑 하여 y축을 세그먼트 트리 구간합에 업데이트 시키는 작업을 순서대로 하는데이 때 이 작업은 전단계의 점들을 반드시 포함하게 되므로 모든점에 대해서 이 작업을 반복하는 것이다. 이 때 처음에는 최대 구간합을 구하기 위해서 이미 업데이트 된 모든 점이랑 비교하여 구간합의 최댓값을 구했는데 이렇게 할 경우 한점에서 업데이트한 후 구간합의 최댓값을 구하는데 O(NlogN) 여기에 .. 더보기