C++ / 3020 / 개똥벌레 ( 누적합 )

https://www.acmicpc.net/problem/3020문제 요약개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔습니다. 동굴의 길이는 N미터이고, 높이는 H미터입니다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장합니다.아래 그림은 길이가 14미터이고 높이가 5미터인 동굴입니다. (예제 그림)이 개똥벌레는 장애물을 피하지 않습니다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴합니다.위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개입니다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말합니다)하지만, 첫 번째 구간이나 다섯 번째 구간으로..

• format_list_bulleted Prefix Sum
• · 2025. 3. 25.
• textsms

C++ / 10986 / 나머지 합 ( 누적 합 )

https://www.acmicpc.net/problem/10986문제 요약수 N개 A1, A2, ..., AN이 주어집니다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성해야합니다.즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 합니다.문제 풀이1. 나머지별로 개수를 카운트 하기 위해서 cnt 배열을 넉넉하게 만듭니다.2. 수를 입력 받음과 동시에 누적합을 만들어 갑니다.3. 누적합을 m으로 나눴을때 나머지 개수를 세어줍니다.4.  cnt[i]는 누적합을 m으로 나눴을 때 나머지가 i인 경우가 몇 번 발생했는지 카운트한 값입니다. 이때, 같은 나머지를 가진 두 누적합을 고르면 그 두 누적합의 차이..

• format_list_bulleted Prefix Sum
• · 2025. 3. 20.
• textsms