반응형 알고리즘 PS/시뮬레이션3 [백준] 11986번 - 나머지 합(Java)(△) https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 1. 먼저 구간 합 배열 D[N]을 구성한다. 2. 구간 합 배열을 순회하면서 M으로 나눠지는 요소를 찾아서 카운트 한다. 3. D배열 첫 인자부터 순회를 하면서 자기보다 작은 구간 합 배열을 뺐을 때 M으로 나눠지는 요소를 찾아서 카운트 한다. - D[i] - (D[0] ~ D[i-1]) 더보기 import java.io.BufferedReader.. 2022. 12. 28. [백준] 11660번 - 구간 합 구하기5(△) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 1. 구간합을 구하기 위해서 가로 기준으로 더해 나가는 합산 테이블 하나, 세로 기준으로 더해나간 합산 테이블 하나해서 총 2개를 준비한다. 2. 2차원 배열의 구간합 배열을 어떤 식으로 구성하느냐가 이 문제를 푸는 열쇠이다. * 점화식 D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j] 3. DP테이블(구.. 2022. 12. 26. [백준] 11659번 - 구간 합 구하기 4(Java)(○) https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 1. 구간합 구하는 공식을 사용하면 된다. 2. 입력합수에서 수를 입력 받을 때마다 누적합을 구해서 구간합 배열을 미리 만들자. * 합 배열 공식 S[i] = S[i-1] + A[i] * 구간 합 공식 A[i] ~ A[j] 사이의 합을 구하려면 S[j] - S[i-1] import java.io.BufferedReader; import java.io.InputStreamRe.. 2022. 12. 26. 이전 1 다음 반응형
