인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

인프런 커뮤니티 질문&답변

힌턴님의 프로필 이미지
힌턴

작성한 질문수

Do it! 알고리즘 코딩테스트 with Python

[구간 합 실전 문제] 나머지 합 구하기 (백준 10986)

나머지 합 구하기 핵심 아이디어 문의

작성

·

97

0

안녕하세요. 나머지 합 구하기 핵심 아이디어 중 첫 번째

 

(A+B)%C는 ((A%C) + (B%C)) % C와 같다.

 

는 것은 본 문제를 푸는 데에는 직접적 관련이 없는 것 같은데 어떻게 관련이 되어 있는지 궁금합니다.

 

문제가 연속된 부분의 합의 나머지를 구하는 것인데,

(A[i+1] + ... + A[j])%M = (S[j] - S[i])%M

이 되고,

나머지 연산이 linear 연산이기 때문에

(S[j] - S[i])%M = 0이라면

S[j]%M = S[i]%M 이라고 할 수 있을 것 같아서요.

 

이 경우에 핵심 아이디어 2번째, 3번째로도 문제 풀이가 가능한 것 같은데,

핵심 아이디어 1번째는 어떤 역할을 하는지 궁금합니다.

 

감사합니다.

이 되어

답변 1

0

안녕하세요, 인프런 AI 인턴입니다.
User님께서 문의하신 내용은 프로그래밍 학습에 관련된 것이지만, 제공된 정보 내에는 직접적으로 관련된 내용이 없습니다. 따라서, 구체적인 답변을 드리기는 어려우며, 일반적인 관점에서 설명 드리겠습니다.

나머지 합 구하기 문제에서 첫 번째 핵심 아이디어인 (A+B)%C = ((A%C) + (B%C)) % C는 나머지 연산의 성질에 대한 이해를 돕기 위한 것입니다. 연속된 부분의 합의 나머지를 구하는 문제에서는 나머지 연산이 선형적으로 이루어지는 것이 중요한데, 이 성질을 이용하여 부분합의 나머지가 같다는 것을 이해하기 위한 기반이 됩니다.

즉, 1번째 핵심 아이디어는 나머지 연산의 분배 법칙을 이해하고 이를 문제에 적용하는 데 초점을 맞춰 나머지 문제를 푸는 데 있어서 다양한 접근 방식과 아이디어를 제공하는데 그 목적이 있습니다. 실제 문제 풀이에 직접적으로 적용되지 않더라도, 나머지 연산을 이해하는 데 도움을 줄 수 있습니다.

감사합니다.

힌턴님의 프로필 이미지
힌턴

작성한 질문수

질문하기