(백준/c++) 11660 - 구간 합 구하기 5

11660번: 구간 합 구하기 5 (acmicpc.net)

11660번: 구간 합 구하기 5

다이나믹 프로그래밍

 

1. "11659 - 구간 합 구하기4"를 2차원으로 변형한 문제라고 접근했다.

2. 동일한 크기의 행렬을 하나 더 만들어 입력을 받는 동시에 이전의 합과 현재값을 더하여 index 1 ~ index 현재까지의 합을 구해주었다. 

 

3. begin : (x1, y1)  end: (x2, y2) 로 구분하여 end부터 begin까지의 합을 구해주었다. 

동적 계획법은 Bottom-Up, Top-Down등 다양한 해답이 많으니 참고만 해주면 좋겠습니다..