9839. 최고의 쌍 D3(C++)

※ SW expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

N개의 양의 정수가 주어졌을 때, 이들 중 정확히 서로 다른 두 개의 정수 쌍을 고르려고 한다.

 

이 때, 두 정수를 고르는 데 있어서 특별한 제약 조건이 존재한다.
고른 서로 다른 두 정수를 x, y라고 하면, 두 정수의 곱 x*y는 10진수로 읽었을 때 증가하면서도 연속한 숫자들로 이루어져야 한다.
예를 들어 2, 23, 23456, 56789는 제약 조건을 만족하고, 21, 54321, 67890, 89012, 88, 889, 79는 제약 조건을 만족하지 않는다.

 

이 조건을 만족하는 모든 쌍 중, 두 정수의 곱이 최대화되는 쌍을 “최고의 쌍” 이라고 부른다.
최고의 쌍이 존재하는지, 존재한다면 이 쌍의 곱은 얼마인지 계산하는 프로그램을 작성해보자.

 

[입력]
첫 번째 줄에 테스트 케이스의 수 TC가 주어진다.
이후 TC개의 테스트 케이스는 각각 다음과 같은 구성과 조건을 따른다.

 

        > 첫 번째 줄에 주어지는 정수의 개수 N 이 주어진다. (1 ≤ N ≤ 1000)

 

        > 두 번째 줄에 N개의 양의 정수가 주어진다. 이 정수들은 각각 1 이상 10000 이하이다. 이 정수들은 모두 서로 다르다.

 

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

각 테스트 케이스마다 최고의 쌍의 두 수의 곱을 출력한다.
만약, 제약 조건을 만족하는 쌍이 존재하지 않는 경우는 -1을 출력한다.

 

그냥 DFS로 모든 쌍 한번 돌려보고 조건 맞는지 보면 된다.

 

#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
int MAP[1000],ans,n;
 
 
void solve(int idx, int next)
{
    if(next == n ) return;
    int temp = MAP[idx] * MAP[next];
    int store = temp,a = temp%10;
    bool isPossible = true;
    temp/=10;
    while(temp)
    {
        int b = temp%10;
        if(a - b!=1)
        {
            isPossible = false;
            break;
        }
        a = b;
        temp/=10;
    }
    if(ans<store && isPossible) ans = store;
    solve(idx, next + 1);
 
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tc;
    cin>>tc;
    for(int t=1;t<=tc;t++)
    {
        ans = -1;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>MAP[i];
        }
        for(int i=0;i<n-1;i++)
            solve(i,i+1);
 
        cout<<'#'<<t<<' '<<ans<<'\n';
    }
    return 0;
}