[BOJ] 10986. 나머지 합 - JAVA
🔗 문제 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 💻 풀이 및 코드 문제 유형 : 수학, 누적합 주어진 배열 중 구간(i, j) 합 이 M 으로 나누어 떨어져는 구간의 갯수를 구하는 문제 풀이 시간 복잡도 : O (N) 문제를 풀기 앞서, 아래의 모듈러 연산의 분배 법칙을 알고 있어야 한다. 문제에 나와있는 '연속된 부분 구간의 합이 M 으로 나누어 떨어지는' 이라는 의미를 생각해보자. 어떠한 구간 [a, b] 에 대해 '[a, b] 구간합 == [1, b..
2023. 3. 15.
[BOJ] 1912. 연속합 - JAVA
🔗 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 💻 풀이 및 코드 문제 유형 : 다이나믹 프로그래밍 요약 : 연속된 구간의 합의 최댓값 풀이 DP 를 풀 때 나는 N 개의 숫자가 주어졌을 때 N 번째의 해당하는 답을 구하기 위해서 첫번째만 숫자가 주어졌을 때, 다음 두 번째 숫자가 주어졌을 때, 세번째 숫자가 주어졌을 때의 답을 차례대로 유추한다. 예제를 보면 [10, -4, 3, 1, 5, 6, -35, 12, 21, -1] 가 주어졌다. 10..
2023. 3. 13.
