[BOJ] 나머지 합 10986번 C++

2024. 3. 28. 15:09· Algorithm

 

 

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

 

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

 

접근 방식

 

너무 어려워서 다른 블로그 글을 참고했는데도 잘 이해가 안간다..

일단 접근 방식은 모듈러 연산이라고 한다.

(A%M) == (B%M) 일때, A-B는 M의 배수이다!!!!

따라서 배열의 합을 구하면서 합을 M으로 나눈 값을 pSum에 저장해두고

pSum에 중복되는 값이 있다면 M의 배수를 만들 수 있는 구간 즉, 합이 M으로 떨어지는 구간이 생길 수 있으므로 

ans 변수에 저장해두는 식으로 풀이를 진행하였다..

 

 

 

알겠으면서 모르겠는...문제이다ㅠ

 

 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int N,M;
ll pSum[1004];

int main() {
    cin>>N>>M;
    long long total = 0, ans = 0;
    int x;
    pSum[0] = 1;
    for(int i=1; i<=N; i++) {
        cin>>x;
        total += x;
        ans += pSum[total % M];
        pSum[total % M]++;
    }

    cout<<ans;

}

'Algorithm' 카테고리의 다른 글

[BOJ] 겹치는 건 싫어 20922번 C++  (0) 2024.04.02
[BOJ] 블로그 21921번 C++  (0) 2024.03.31
[BOJ] 수들의 합 4 2015번 C++  (0) 2024.03.26
[BOJ] 귀찮아 (SIB) 14929번 C++  (0) 2024.03.25
[BOJ] 주지수 15724번 C++  (1) 2024.03.22
'Algorithm' 카테고리의 다른 글
  • [BOJ] 겹치는 건 싫어 20922번 C++
  • [BOJ] 블로그 21921번 C++
  • [BOJ] 수들의 합 4 2015번 C++
  • [BOJ] 귀찮아 (SIB) 14929번 C++
따봉치치
따봉치치
따봉치치
김치치의개발블로그
따봉치치
전체
오늘
어제
  • 분류 전체보기 (359)
    • 면접질문 (4)
    • CS (50)
    • FE (116)
      • Javascipt (16)
      • Typescipt (6)
      • React (16)
      • CSS (5)
      • Nextjs (1)
      • 리뷰 (70)
    • Algorithm (181)
    • ETC (3)
      • Bootcamp (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 모던 자바스크립트 딥다이브
  • 자바스크립트
  • 그리디
  • 백트래킹
  • CS
  • Fe
  • 문자열
  • 투 포인터
  • dp
  • Stack
  • 완전탐색
  • 스택
  • BFS
  • typescript
  • C++
  • 우선순위 큐
  • 자료구조
  • Greedy
  • 알고리즘
  • 그래프 탐색
  • BOJ
  • react
  • 누적합
  • 리액트
  • 데이터베이스
  • 백준
  • 모던 리액트 딥다이브
  • TOPCIT
  • javascript
  • 탐욕 알고리즘

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
따봉치치
[BOJ] 나머지 합 10986번 C++
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.