개발일지/Algorithm
백준 - 11660 구간 합 구하기 5 [DP]
E-room
2023. 9. 23. 00:59
728x90
14719번: 빗물
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치
www.acmicpc.net
1. 문제 요약
N x N의 표가 주어지고 좌표가 주어지면, 그 구간의 합계를 구하는 문제이다.
2. 접근 방법
다이내믹 프로그래밍을 이용하여 각각의 구간별 합을 미리 구해놓는다. (DP 테이블)
예를 들어, DP 테이블의 (2,2)의 위치는
기존테이블의 (2,2) + DP(2,1) + DP(1,2) - DP(1,1)이다
즉, 원하는 위치의 수 + DP테이블의 위 + 좌 - 겹치는 구간이다
- DP테이블은 (N+1) x (N+1)로 생성하면 편리하다. (메모리를 더 잡아먹기 때문에 필수는 아님)
좌표가 주어지면 앞서 구해놓은 DP 테이블을 이용하여 계산한다.
(2, 2), (3, 4)을 구해야 할 경우 (3, 4) - (1, 4) - (3, 1) + (1, 1)이다.
(x1, y1), (x2, y2)가 주어질 경우
목표 = (x2, y2) - (x1 -1, y2) - (x2, y1 -1) + (x1 -1, y1 -1)로 나타낼 수 있다.
3. 파이썬
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
# dp 테이블 세팅
for i in range(N):
data = list(map(int, input().split()))
for j in range(N):
dp[i+1][j+1] = data.pop(0) + dp[i][j+1] + dp[i+1][j] - dp[i][j]
# 정답 계산 및 출력
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
answer = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
print(answer)
4. 자바
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// dp 테이블 세팅
int[][] dp = new int[N + 1][N + 1];
for (int i = 1; i < dp.length; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j < dp[i].length; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + Integer.parseInt(st.nextToken());
}
}
// 정답 계산 및 입력
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
int answer = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
bw.write(answer + "\n");
}
// 출력
bw.flush();
bw.close();
}
5. 전체 코드
728x90