개발일지/Algorithm
백준 - 11660 구간 합 구하기 5 [DP]
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)로 생성하면 편리하다..
