코딩테스트 -- 주사위 고르기 - (프로그래머스 / C++)

 

 

프로그래머스

 

 

문제요약!

---

 A 와B가 n개의 주사위 중 절반을 선택하여 굴릴때, 굴려나온 모든 수의 합의크기로 B보다 A가 크도록, 

A가 이길수 있는 확률이 가장 높은 주사위의 선택 리스트를 구하는 문제!

 

특이한 점은 각 면에 일반적인 숫자들이 아닌 리스트의 수들로 각 주사위마다 숫자가 다르다는 점!

---

 

상당히 까다로운 문제처럼 보입니다...

 

그래도 풀어서 생각해보면 

1. N개의 주사위중 절반 선택

2. 선택한 주사위들을 굴려 승리할 확률 구하기

 

 

이렇게 2가지로 그렇게 복잡하진 않아 보입니다. 

경우의 수는 되게 많아 보이지만....

 

 

최대의 경우의 수를 계산해보면 

최대 주사위의 갯수가 10이라고 했을때 각각의 사람은 5개의 주사위를 굴리게 되므로 

10개중 5개 선택 경우의 수=  10C5  = 252  

 

합을 구하기 위해서

선택한 주사위들의 합 경우의 수 = 6^5

 

 

이렇게 252*6^5 만큼의 계산만 하면 가능해 보입니다!

 

 

 

그럼 이제 코드 시작!

 

 

일단 저는 1. 전체 주사위중 몇번의 주사위를 선택하는지에 대한 함수를 만들어 주었습니다.

 

깊이 탐색을 이용해서  count에 맞게 주사위를 골라 주었고,

이렇게 선택한 주사위의 번호 리스트를 각각 ListA, ListB에 저장해 주었습니다. 

 

만약 4개의 다이스를 가지고 아래 함수를 실행한다면

ListA = [[0,1], [0,2], [0,3]...]

ListB = [[2,3], [1,3], [1,2]...]

 

이런식으로 저장되게 됩니다. 

vector<vector<int>> ListA;
vector<vector<int>> ListB;
....


void MakeList(int now,int count, vector<int>A, vector<int>B) {
// now 현재위치 , count 고를 수 

    int tempA = A.size();
    int tempB = B.size();


    if (tempA == count && tempB == count) {
        ListA.push_back(A);
        ListB.push_back(B);
        return;
    }

    if (tempA == count) {
        B.push_back(now);
        MakeList(now + 1, count, A, B);
    }
    else if (tempB == count) {
        A.push_back(now);
        MakeList(now + 1, count, A, B);
    }
    else {
        A.push_back(now);
        MakeList(now + 1, count, A, B);
        A.pop_back();

        B.push_back(now);
        MakeList(now + 1, count, A, B);
        B.pop_back();

    }
}

 

 

 

다음은 이렇게 선택한 주사위들의 가능한 합들을 모두 구해주는 함수를 만들어 주었습니다.

 

만약 1,2,6번 주사위를 선택했다면 아래 함수를 통해 모든 경우의 수 6^3의 합을 구해

각각 SumA, SumB로 넘겨주었습니다.

void sumCal(int count, int maxSum, vector<int> List, vector<vector<int>> dice) {

    if (count == 0) {

        if (sortnum == 0) {
            SumA.push_back(maxSum);
        }
        else {
            SumB.push_back(maxSum);
        }

        return;
    }


    for (int i = 0; i < dice[List[count-1]].size(); i++) {
        sumCal(count - 1, maxSum + dice[List[count-1]][i], List, dice);
    }
}

 

 

 

 

이제 구한 합들을 이용해서 확률을 구해줄 차례입니다!

 

아래의 diceCal함수를 통해 SumA, SumB의 숫자를 비교해주고,

확률을 구할 필요없이 승리수만 체크 해주어 답을 구해주었습니다. 

(전체 경우의수는 같기에, 승리 수의 크기정도가 확률의 크기정도와 같습니다.)

 

// 몇번째 다이스에서 숫자 어떤걸 뽑았는지 해서 모든 합을 구해야할듯
vector<int> diceCal(vector<vector<int>> dice) { // 현재 골라놓은 다이스리스트들

    int Maxvictory = 0;
    vector<int>MaxList; // 가장 합이 

    for (int i = 0; i < ListA.size(); i++) {

        sortnum = 0;
        sumCal(choice, 0, ListA[i], dice);

        sortnum = 1;
        sumCal(choice, 0, ListB[i], dice);

        // 서로의 합이 나온 부분

        int maxTemp = 0;

        for (int j = 0; j < SumA.size(); j++) {

            for (int k = 0; k < SumB.size(); k++) {
                if (SumA[j] > SumB[k]) {
                    maxTemp += 1;
                }
            }
        }

        if (maxTemp > Maxvictory) { // 승리할 확률 최신화
            Maxvictory = maxTemp;

            sort(ListA[i].begin(), ListA[i].end());
            MaxList= ListA[i];
        }

        SumA.clear();
        SumB.clear();
    }

    return MaxList;

}

 

 

그리고 마지막으로 다이스는 1번 부터 시작한다는 점을 고려하여 +1처리를 하여 리턴 해주면 끝!

vector<int> solution(vector<vector<int>> dice) {
    vector<int> answer;
    vector<int> A, B;


    int n = dice.size();
    choice = n / 2;

    MakeList(0, choice, A, B); // 시작 위치 / 선택할 주사위 수 


    answer=diceCal(dice);

    for (int i = 0; i < answer.size(); i++) {
        answer[i] += 1;
    }


    return answer;
}

 

 

조금 침착하게 풀었다면 금방 풀었을 문제...

경우의 수가 크다고만 생각해서 좀 더 나은 방법을 찾는데 시간을 허비했네요...

 

과정이 약간 복잡했지만 순서대로 완전탐색을 통해 결과를 내는 문제였던것 같습니다!

 

 

 

 

 

 

ALL

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;


// 절반을 선택할때 선택한 리스트들
vector<vector<int>> ListA;
vector<vector<int>> ListB;

vector<int> SumA;
vector<int> SumB;

int sortnum = 0;
int choice = 0;


void MakeList(int now,int count, vector<int>A, vector<int>B) {// now 현재위치 , count 고를 수 

    int tempA = A.size();
    int tempB = B.size();


    if (tempA == count && tempB == count) {
        ListA.push_back(A);
        ListB.push_back(B);
        return;
    }

    if (tempA == count) {
        B.push_back(now);
        MakeList(now + 1, count, A, B);
    }
    else if (tempB == count) {
        A.push_back(now);
        MakeList(now + 1, count, A, B);
    }
    else {
        A.push_back(now);
        MakeList(now + 1, count, A, B);
        A.pop_back();

        B.push_back(now);
        MakeList(now + 1, count, A, B);
        B.pop_back();

    }
}

void sumCal(int count, int maxSum, vector<int> List, vector<vector<int>> dice) {

    if (count == 0) {

        if (sortnum == 0) {
            SumA.push_back(maxSum);
        }
        else {
            SumB.push_back(maxSum);
        }

        return;
    }


    for (int i = 0; i < dice[List[count-1]].size(); i++) {
        sumCal(count - 1, maxSum + dice[List[count-1]][i], List, dice);
    }
}


// 몇번째 다이스에서 숫자 머를 뽑았는지 해서 모든 합을 구해야할듯
vector<int> diceCal(vector<vector<int>> dice) { // 현재 골라놓은 다이스리스트들

    int Maxvictory = 0;
    vector<int>MaxList; // 가장 합이 

    for (int i = 0; i < ListA.size(); i++) {

        sortnum = 0;
        sumCal(choice, 0, ListA[i], dice);

        sortnum = 1;
        sumCal(choice, 0, ListB[i], dice);


        // 서로의 합이 나온 부분

        int maxTemp = 0;



        for (int j = 0; j < SumA.size(); j++) {

            for (int k = 0; k < SumB.size(); k++) {
                if (SumA[j] > SumB[k]) {
                    maxTemp += 1;
                }
                
            }
        }
        if (maxTemp > Maxvictory) { // 승리할 확률 최신화
            Maxvictory = maxTemp;

            sort(ListA[i].begin(), ListA[i].end());
            MaxList= ListA[i];
        }

        SumA.clear();
        SumB.clear();
    }

    return MaxList;

}

vector<int> solution(vector<vector<int>> dice) {
    vector<int> answer;
    vector<int> A, B;


    int n = dice.size();
    choice = n / 2;

    MakeList(0, choice, A, B); // 시작 위치 / 선택할 주사위 수 


    answer=diceCal(dice);

    for (int i = 0; i < answer.size(); i++) {
        answer[i] += 1;
    }


    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!