9839. 최고의 쌍

문제 (요약)

주어진 입력에서 고른 두 수의 곱을 출력하라. 이 곱은 증가하는 연속숫자(예, 2, 23, 23456, 456 등)로 이루어져야 한다. 이 값이 여러 개인 경우 최댓값을 출력하고 조건에 맞도록 두 수를 고를 수 없을 경우 -1을 출력하라

접근

입력으로 10^3개 이하의 수열이 주어지므로 이들을 조합하여 곱을 구하면 10^6 개의 곱을 얻고 이들 값이 각각 조건을 만족하는지 확인하면 된다. 이는 충분히 작은 숫자이므로 전수조사(O(N^2))로 풀이할 수 있다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>

FILE* stream;
using namespace std;

int T, N;

int main(void) {
    cin >> T;

    for (int t = 1; t <= T; t++) {
        int ret = -1; 
        cin >> N;
        vector<int> arr = vector<int>(N);
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int num = arr.at(i) * arr.at(j);

                // 1의 자리 숫자
                int digit = num % 10;
                bool chk = true;

                num = num / 10;
                while (num > 0) {
                    if (digit - 1 == num%10) {
                        digit--;
                    } else {
                        chk = false;
                        break;
                    }
                    num = num / 10;
                }
                if (chk == true && ret < arr.at(i) * arr.at(j)) {
                    ret = arr.at(i) * arr.at(j);;
                }
            }
        }

        cout << "#" << t << " " << ret << endl;
    }
    return 0;
}