구간합구하기4 검색 결과
1 개의 검색 결과가 있습니다.
PS/BOJ

백준 11659번 : 구간 합 구하기 4 풀이 (Java) - DP

www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net dp 에 익숙하다면 금방 풀 것이다. 10분도 안 걸린듯하다. Solution 1. N, M 이 모두 최대가 100,000 이다. 만약 합을 구할 구간을 입력받을 때 마다 반복문으로 돌린다고 해도,1~100000 이 100000번 나온다면 100억 회를 해야 한다. 당연히 시간 초과가 뜰 것이다. 2. 즉 이 문제는, N 만큼의 배열의 숫자들을 입력 받을 때, dp 배열에다가 합을 미리 ..

2021. 3. 27. 18:46