https://programmers.co.kr/learn/courses/30/lessons/92344 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr 2022 KAKAO BLIND RECRUITMENT 파괴되지 않은 건물 문제 C++ 풀이입니다. 필요한 배경지식 누적합 참고하면 좋음 : 누적합의 확장, imos법 문제 해결 방법 문제에서 skill을 통해 ..
https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 필요한 배경지식 누적 합 : prefix sum 문제 해결 방법 누적합 알고리즘을 이용하여 1번째부터 n번째까지의 수의 합을 S[n]이라고 나타내면 i번째 수부터 j번째까지 수들의 합 S[i,j]를 S[j] - S[i-1]로 나타낼 수 있습니다. 문제 조건에서 S[i,j] % M이 0인 (i,j)쌍을 구해야 하므로 누적합을 이용하여 식으로 표현하면 ..