(C++) - 백준(BOJ) 1225번 : 이상한 곱셉 답

www.acmicpc.net/problem/1225

1225번: 이상한 곱셈

문자열 다루는 문제였습니다.

풀이방법

 정답 변수에 O(N^2)의 시간복잡도로 모든 조합을 곱한 뒤 더해주면 됩니다. 1만자리까지 곱의 결과를 더하므로 int범위를 초과할 수 있기 때문에 ans의 자료형을 long long으로 해주시면 됩니다.

 예를 들어 a,b string이 1만자리라면 나올 수 있는 경우의 수가 1만 * 1만 = 1억개가 됩니다. 따라서 a = "9999999..."

b = "9999999..." 식으로 되어 있다면 81 * 1억 81억이 되므로 int범위인 21억을 초과합니다.

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll ans;
string a, b;
int main(){
    cin >> a >> b;
    for(int i = 0; i < a.size(); i++)
        for(int j = 0; j < b.size(); j++)
            ans += (a[i] - '0') * (b[j] - '0');
    cout << ans <<'\n';
}