백준 11441번
-
백준 11441번 : 합 구하기다이나믹프로그래밍(DP) 2018. 6. 18. 14:50
https://www.acmicpc.net/problem/11441 1. 문제 N개의 수 A1, A2, ..., AN이 입력으로 주어진다. 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 2. 알고리즘 키워드 - 부분 합최초의 입력 받은 배열은 위 처럼 10, 20, 30, 40, 50 으로 이루어 져있는 배열이다. 배열의 부분합을 만들기 위해 0 번째 배열을 추가하고 배열[i-1] + 배열[i] 부분 합을 구한다. 문제 에서 1번과 4번 배열의 합을 구하라고 나와 있다. 1번 부터 N 까지는 모두 계산이 되어 있음으로 위와 같이 답을 도출 할 수 있다. 두번 째 예제에서는 2번 부터 4 까지의 합을 계산 해야 한다.2번 의 부분합은 30 임으로 ..