문제 설명수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.https://www.acmicpc.net/problem/10986 제한 사항 풀이문제를 요약하면, 연속한 부분의 합이 M으로 나누어 떨어지는 (i, j)의 쌍의 개수를 구하는 것이다. 누적합을 이용하면 간단하게 풀 수 있어 보이지만 사실은 그렇지 않다.누적합을 이용하여 (i, j)의 모든 쌍을 구한다고 가정하면 N이 최대 $10^6$이기 때문에 시간초과가 발생한다.따라서, 다른 풀이가 필요하다. 문제의 핵심은 mod연..
정답 비율이 40%라 도전해봤는데 문제가 짧아서 당황했다. 문제를 읽어보니 문제 제목과 똑같이 입력받은 수로 어떠한 수를 나누었을 때 몫과 나머지가 같은 수들의 합을 구하면 되는 간단한 문제였다. 이런 문제 정답 비율이 왜 이렇게 낮을까 생각하고 문제 풀이를 시작했다. 입력받은 수를 n이라 했을 때 어떠한 수를 나누는 상황에서 나머지가 생기는 경우는 n-1가지의 경우이다. ( 나머지는 나누는 수 보다 무조건 작고, 1~n-1까지의 수이다. ) 이러한 원리로 1부터 n-1까지 어떠한 수의 몫과 나머지가 같은 수를 만들어 더해주면 될 거라 생각했다. 아래는 처음에 작성한 Java 코드이다. import java.util.Scanner; public class SameMod { public static voi..
