배열과 세 개의 값 — 왼쪽 값 L, 오른쪽 값 R, 그리고 소수 P가 입력으로 주어졌을 때, L부터 R 사이에 있는 요소들의 곱을 계산한 후 소수 P로 나눈 나머지(모듈로)를 구해 출력하는 것이 이 글의 목표입니다.
아래 그림처럼 여러 요소로 이루어진 배열이 있고, 왼쪽 값 L은 2, 오른쪽 값 R은 6이라고 가정해 보겠습니다. 프로그램은 이 두 위치 사이에 있는 요소들의 곱을 계산해야 합니다.
예시
입력 : A[] = { 1, 2, 3, 4, 5, 6 }
P = 29, L = 2, R = 6
출력 : 24
입력 : A[] = { 1, 2, 3, 4, 5, 6 }
L = 2, R = 5, P = 113
출력 : 7
첫 번째 예시에서 인덱스 2부터 6까지의 요소는 2 × 3 × 4 × 5 × 6 = 720이며, 720을 29로 나눈 나머지는 24입니다. 두 번째 예시에서는 2 × 3 × 4 × 5 = 120이고, 120을 113으로 나눈 나머지는 7이 됩니다.
프로그램의 접근 방식
- 정수형 배열과 왼쪽 값(L), 오른쪽 값(R), 소수 값(P)을 입력받습니다.
- 왼쪽 값부터 오른쪽 값까지 배열 요소를 차례대로 순회합니다.
- 순회하면서 각 요소와의 곱셈 결과를 임시 변수에 누적 저장합니다.
- 매 단계마다 소수 값으로 모듈로(나머지) 연산을 수행해 값이 지나치게 커지는 것을 방지합니다.
- 순회가 끝나면 최종 결과를 출력합니다.
알고리즘
Start
Step 1 → 곱을 계산하는 함수 선언
int calculateProduct(int A[], int L, int R, int P)
정수형 변수 i 선언
L = L − 1 설정
R = R − 1 설정
정수형 변수 ans = 1로 초기화
반복문 : i = L 부터 i ≤ R 까지, i는 1씩 증가
ans = ans * A[i]
ans = ans % P
반복문 종료
return ans
Step 2 → main() 함수에서
배열 선언 : int A[] = { 1, 2, 3, 4, 5, 6 }
변수 선언 : int P = 29
변수 선언 : int L = 2, R = 6
A, L, R, P를 이용해 결과 출력
Stop
C 코드 구현
#include <stdio.h>
int calculateProduct(int A[], int L, int R, int P) {
int i;
// 배열 인덱스는 0부터 시작하지만
// L과 R은 1부터 시작하므로 1씩 빼줍니다.
L = L - 1;
R = R - 1;
int ans = 1;
for (i = L; i <= R; i++) {
ans = ans * A[i];
ans = ans % P;
}
return ans;
}
int main() {
int A[] = { 1, 2, 3, 4, 5, 6 };
int P = 29;
int L = 2, R = 6;
printf("%d\n", calculateProduct(A, L, R, P));
return 0;
}
출력 결과
24
핵심 포인트
곱셈 결과는 범위에 포함된 요소 개수가 늘어날수록 기하급수적으로 커지기 때문에, 중간에 정수 오버플로우가 발생할 위험이 있습니다. 따라서 매 반복마다 소수 P로 나머지 연산을 수행하면 최종 결과의 나머지 값은 그대로 유지되면서도 오버플로우 없이 안전하게 계산할 수 있습니다. 또한 L과 R은 1부터 시작하는 반면 배열 인덱스는 0부터 시작하므로, 두 값을 각각 1씩 감소시켜 인덱스에 맞춰주는 점도 주목할 필요가 있습니다.