BOJ 25369 : 카드 숫자 곱을 최소로 만들기

• 문제 링크 : boj.kr/25369
• 난이도 : S1
• 태그 : 브루트포스

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    int pa = 1;
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        pa *= input;
    }
    
    int l = pow(9, n);
    for(int i = 0; i < l; i++) {
        vector<int> arr(n);
        int curr = i;
        for(int d = 0; d < n; d++) {
            arr[d] = curr % 9 + 1;
            curr /= 9;
        }
        reverse(all(arr));
        int pb = 1;
        for(auto e : arr) pb *= e;
        if(pb > pa) {
            for(auto e : arr) cout << e << " ";
            return 0;
        }
    }
    cout << -1;
    return 0;
}

---

풀이

선택한 카드 B의 상태를 다음의 식을 이용하여 하나의 키로 나타낼 수 있다.

$\sum\limits_{k=0}^{n}{(B[k]-1) * 9^k}$

키는 0~9^n-1의 값을 가지고, 키가 오름차순이면 카드의 상태 역시 오름차순이다.

따라서 키에 대한 순차적인 탐색을 통해 답을 구할 수 있다.