728x90
반응형
11660번: 구간 합 구하기 5 (acmicpc.net)
11660번: 구간 합 구하기 5
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네
www.acmicpc.net
다이나믹 프로그래밍
1. "11659 - 구간 합 구하기4"를 2차원으로 변형한 문제라고 접근했다.
2. 동일한 크기의 행렬을 하나 더 만들어 입력을 받는 동시에 이전의 합과 현재값을 더하여 index 1 ~ index 현재까지의 합을 구해주었다.
3. begin : (x1, y1) end: (x2, y2) 로 구분하여 end부터 begin까지의 합을 구해주었다.
동적 계획법은 Bottom-Up, Top-Down등 다양한 해답이 많으니 참고만 해주면 좋겠습니다..
728x90
반응형
'📃 coding test > ◽ 백준' 카테고리의 다른 글
| (백준/c++) 2559 - 수열 (0) | 2022.06.27 |
|---|---|
| (백준/c++) 10986 - 나머지 합 (0) | 2022.06.24 |
| (백준/c++) 11659 - 구간 합 구하기 4 (0) | 2022.06.23 |
| (백준/c++) 24444~24445 너비 우선 탐색 1~2 (0) | 2022.06.05 |
| (백준/c++) 24480 - 알고리즘 수업 - 깊이 우선 탐색 2 (0) | 2022.06.04 |
