[프로그래머스/C++] 주사위 고르기 (Lv. 3)

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#define ll long long

using namespace std;

vector<ll> a; // a가 선택하는 주사위
vector<ll> b; // b가 선택하는 주사위

vector<ll> asum; // a가 전체 주사위를 다 굴려서 가능한 합
vector<ll> bsum; // b가 전체 주사위를 다 굴려서 가능한 합

vector<vector<int>> dices;

void asum_dfs(ll idx, ll sum) { // 인덱스 0번까지 봤을 때 합이 sum이다. 
    if (idx == a.size() - 1) {
        asum.push_back(sum);
        return;
    } 
    
    ll dice = a[idx + 1];
    for (ll i = 0; i < 6; i++) {
        asum_dfs(idx + 1, sum + dices[dice][i]);
    }
}

void bsum_dfs(ll idx, ll sum) { // 인덱스 0번까지 봤을 때 합이 sum이다. 
    if (idx == b.size() - 1) {
        bsum.push_back(sum);
        return;
    } 
    
    ll dice = b[idx + 1];
    for (ll i = 0; i < 6; i++) {
        bsum_dfs(idx + 1, sum + dices[dice][i]);
    }
}

ll cmpab() {
    ll cnt = 0;
    for (ll i = 0; i < asum.size(); i++) {
        for (ll j = 0; j < bsum.size(); j++) {
            if (asum[i] > bsum[j])
                cnt++;
        }
    }
    
    return cnt;
}

vector<int> solution(vector<vector<int>> dice) {
    dices = dice;
    
    ll n = dices.size();
    vector<ll> sub(n, 0);
    for (ll i = 0; i < n / 2; i++) {
        sub[n - 1 - i] = 1;
    }
    
    ll maxw = -1;
    vector<int> answer;
    do {
        a.clear(); a.resize(0);
        b.clear(); b.resize(0);
        asum.clear(); asum.resize(0);
        bsum.clear(); bsum.resize(0);
        
        for (ll i = 0; i < n; i++) {
            if (sub[i] == 0) {
                a.push_back(i);
            } else {
                b.push_back(i);
            }
        }
    
        for (ll i = 0; i < 6; i++) {
            ll d = a[0];
            asum_dfs(0, dices[d][i]);
        }
        
        
        for (ll i = 0; i < 6; i++) {
            ll d = b[0];
            bsum_dfs(0, dices[d][i]);
        }
        
        ll res = cmpab();
        if (res > maxw) {
            maxw = res;
            answer.clear(); answer.resize(0);
            
            sort(a.begin(), a.end());
            for (ll i = 0; i < a.size(); i++) {
                answer.push_back(a[i] + 1);
            }
        }
    
    } while (next_permutation(sub.begin(), sub.end()));

    return answer;
}

전략

브루트포스로 풀었다.

모든 경우의 수
1, 2를 가져가서, 36개의 경우의 수
brouth force?
최대일 때 A가 가져가는 주사위의 수: 5
5^5 = 3125
3125^2 = 9765625
-> 브루트포스 가능!

1. next_permuation()으로 조합 만들어서 벡터 a, b에 담는다.
2. a와 b에 각각 담긴 주사위로 만들 수 있는 모든 합을 asum, bsum에 담는다.
3. asum과 bsum의 모든 원소를 비교하여 asum이 더 큰 개수를 센다.

헷갈렸던 점

A, B가 각각 몇 개의 주사위를 던질지 모르니 모든 합을 구하는 코드를 짜는 게 어려웠다. n개라고 정해져 있으면 n중 for문을 짜면 되는데...
결국 idx 배열을 만들어서 하는 걸로 머리를 굴려봤다.

찾아보니 asum과 bsum을 비교하는 걸 이분탐색으로 구하는 게 모범 답안인 듯하다.
bsum을 정렬하고, asum[i]보다 작은 bsum의 개수를 이분 탐색으로 구할 수 있다.
이분 탐색에서 구하고자 하는 값은, asum[i]보다 작은 bsum 중 최댓값의 인덱스이다.

이분탐색 안 했는데도 풀려서 다행이다. 여기서 시간초과 났으면 이분탐색 못 생각해냈을 듯.