https://www.acmicpc.net/problem/14846 14846번: 직사각형과 쿼리 첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며 www.acmicpc.net 문제 N행 N열로 이루어진 정사각형 행렬 A가 주어진다. 이때, 쿼리를 수행하는 프로그램을 작성하시오. x1 y1 x2 y2: 왼쪽 윗칸이 (x1, y1)이고, 오른쪽 아랫칸이 (x2, y2)인 부분 행렬에 포함되어 있는 서로 다른 정수의 개수를 출력한다. 제한사항 첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 ..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램 작성 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 열심히 종이에 그려가면서 구하려고 했는데 너무 복잡하게 생각한 탓인지 못풀었다. 결국 해설을 듣고 알게되었는데, 내가 처음에 잠깐 생각한 '행별로 누적합 구해서 더하기'가 맞았다. 시간초과날 것 같아서 안해봤는데.. 시간초과 각오하고 시도해보는 것도 좋을 것 같다라는 생각이 들었다. 괜히 시간초과 날 것 같다고 다른 방법 생각하다가 더 복잡하게 생각하고 ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 주어진 배열에서 연속해서 3개까지 선택할 수 없고 최댓값을 구하는 문제로 이전에 풀었던 계단오르기(https://www.acmicpc.net/problem/2579)와 비슷한 문제이다. 계단오르기에서는 도착 지점을 무조건 선택해야 하지만 포도주 시식에서는 상관 없다. 그래서 선택하지 않는 경우를 추가하며 경우의 수가 하나 더 늘었다. 초기값 (n = 1, n= 2) dp[1] = glass[1] d..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 상향식 or 하향식으로 푸는 DP 개념을 안다면 금방 쉽게 풀린다. cost 배열과 크기가 같은 2차원의 dp 배열에 dp[i][j]까지의 비용의 합을 저장한다. 1. dp 배열의 0행 : 1번 집의 R, G, B 값을 저장한다. 2. dp 배열의 1 ~ N-1행 - R을 선택할 경우 : 현재의 행에서 R을 선택할 경우의 비용에 이전 행에서 G를 선택했을 경우의 비용의 합과 ..