[백준 25710번] 점수 계산 (C++)

문제링크 : https://www.acmicpc.net/problem/25710

25710번: 점수 계산

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

vector<int> v;
vector<int> v2;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N; cin >> N;
    v.resize(1000);
    for(int i=0; i<N; i++) 
    {
        int n; 
        cin >> n;
        v[n]++; //갯수 체크
    }

    for(int i=1; i<=999; i++) 
    {
        if(v[i] == 1) v2.push_back(i); //단 하나
        else if(v[i] >=2) //중복발생, 2개만 있으면 된다 
        {
            v2.push_back(i);
            v2.push_back(i);
        }
    }

    int result = 0;

    for(int i=0; i<v2.size(); i++)
    {
        for(int j=i+1; j<v2.size(); j++) 
        {
            int tmp = v2[i] * v2[j];
            int sum = 0;

            while(tmp > 0) //한 자릿수 더하기
            {
                sum += tmp % 10;
                tmp /= 10;
            }

            result = max(result, sum);
        }
    }
    cout << result << "\n";
    
}

막연하게 생각하면 이중 반복문을 통해서 전부 검토하면 되지만, N이 10만이라 시간초과가 발생한다.

우리가 보는 수의 범위는 1 ~ 999이므로 이를 이용해야 한다.

 

1번 있는건 1번만 체크하고, 2번 이상 반복되는 것은 딱 2번 까지만 필요하기에 (ex : 5 * 5) 2번만 벡터에 넣어준다.

이후는 그냥 브루트포스로 다 곱해가면서 각 곱해준 값의 자릿수를 더해서 체크하는 것 뿐이다.

 

처음에 반복되는 경우를 아에 제외하고(set) 시작하여 여러번 틀렸다.