[C] 22193번: Multiply
[C] 22193번: Multiply
문제
https://www.acmicpc.net/problem/22193
음이 아닌 두 정수 A와 B의 곱을 계산하는 프로그램을 작성하시오. 두 정수는 10진수로 표기되며, 각각 N자리와 M자리 수입니다.
입력
첫째 줄에 두 수의 길이 N과 M이 공백으로 구분되어 주어집니다. 둘째 줄에는 A가, 셋째 줄에는 B가 주어집니다. 주어지는 수는 0으로 시작하지 않습니다 (불필요한 0이 앞에 오지 않음).
출력
A와 B의 곱을 0으로 시작하지 않게 출력하시오.
제한
- 1 ≤ N, M ≤ 50 000
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | N, M ≤ 4 |
| 2 | 20 | N, M ≤ 9 |
| 3 | 30 | N, M ≤ 5 000 |
| 4 | 30 | 추가 제약조건 없음 |
풀이
큰 정수를 문자열로 받아, 사람이 계산하듯 각 자리수를 곱해 누적한 뒤 자리올림을 처리하는 방식입니다.
구체적으로는
- A의 각 자리와 B의 각 자리를 곱해
res[i + j + 1]에 누적 - 곱셈이 끝난 뒤 뒤에서부터 자리올림 처리
- 앞쪽의 불필요한 0을 건너뛰고 출력
하는 방식으로 구현할 수 있습니다.
코드
#include <stdio.h>
#define MAX 50001#define MAX_RES 100001
char a[MAX], b[MAX];int res[MAX_RES];
int main() { int n, m; scanf("%d %d", &n, &m); scanf("%s", a); scanf("%s", b);
for (int i = n - 1; i >= 0; i--) { int da = a[i] - '0'; for (int j = m - 1; j >= 0; j--) { res[i + j + 1] += da * (b[j] - '0'); } }
for (int i = n + m - 1; i > 0; i--) { res[i - 1] += res[i] / 10; res[i] %= 10; }
int start = 0; while (start < n + m - 1 && res[start] == 0) { start++; }
for (int i = start; i < n + m; i++) { printf("%d", res[i]); } printf("\n");
return 0;}