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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/258709

프로그래머스

풀이

크게 이렇게 볼 수 있다.

1. A가 주사위를 고른다. 나머지 주사위는 B의 것

2. A와 B가 각각 고른 주사위들로 만들 수 있는 모든 합들을 구한다

3. A와 B가 대결하여 A가 이기는 수를 확인한다

 

테스트 케이스 1번을 예시로 들어 살펴보자

 

COMBINATION, Pick dices

다이스 총 개수가 4개라 벡터 0011을 만든다

next_permutation하려면 오름차순정렬 되어있어야 하기 때문에 이렇게 했다.

next_permutation으로 모든 경우의 수를 구해준다 (0011, 0101, 1001, 1100)

여기서 예를 들어 0101의 의미는

A가 2,4번째 다이스를 선택했고 B는 1,3번째 다이스를 얻은 것

 

calculate all possible sums

각각의 다이스로 만들 수 있는 모든 합들을 allSumA, allSumB에 각각 저장한다.

A가 주사위 [1,2,3,4,5,6] 와 [3,3,3,3,4,4]를 고르고

B가 주사위 [1, 3, 3, 4, 4, 4] [1, 1, 4, 4, 5, 5]를 골랐다면 

allSumA= 4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,8,8,8,8,8,8,9,9,9,9,9,9,10,10

allSumB= 2 2 5 5 6 6 4 4 7 7 8 8 4 4 7 7 8 8 5 5 8 8 9 9 5 5 8 8 9 9 5 5 8 8 9 9

이다.

 

calculate A win count

compare함수로 A가 몇번 이기는지 세준다.

그냥 싹다 하나씩 비교했다..

 

 

제일 많이 이길때의 주사위 조합을 저장한 후 출력하면 완성

 

 

코드

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


void findSums(const vector<vector<int>>& vectors, int index, int currentSum, vector<int>& sums) 
{
    if (index == vectors.size()) 
    {
        // all vectors have been processed
        sums.push_back(currentSum);
        return;
    }

    for (int num : vectors[index]) 
    {
        findSums(vectors, index + 1, currentSum + num, sums);
    }
}

int compare(vector<int>A,vector<int>B)
{
    int aWins = 0;
    
    for (int a : A) 
    {
        for (int b : B) 
        {
            if (a > b) {  aWins++;  }
        }
    }
    return aWins;   
}

vector<int> solution(vector<vector<int>> dice) 
{
    
    //COMBINATION////////////////////////////////////////
    int diceSize=dice.size();
    vector<int> combination(diceSize,0);
    for(int i=diceSize/2;i<diceSize;i++)
    {   combination[i]=1;  }
    
    //ANSWER/////////////////////////////////////////////
    int maxWinNum=0;
    vector<int> bestCombination;
    
    //CHECK//////////////////////////////////////////////
    do
    {
        //Pick dices
        vector<vector<int>> diceA,diceB;

        for(int i=0;i<combination.size();i++)
        {
            if(combination[i]==1){diceA.push_back(dice[i]);}
            else{diceB.push_back(dice[i]);}
        }
        
        //calculate all possible sums
        vector<int>allSumA,allSumB;
        findSums(diceA,0,0,allSumA);
        findSums(diceB,0,0,allSumB);
       
        //calculate A win count
        int nowWin=compare(allSumA,allSumB);
        if(nowWin>maxWinNum)
        {
            maxWinNum=nowWin;
            bestCombination=combination;
        }

    }while(next_permutation(combination.begin(),combination.end()));


    //RESULT/////////////////////////////////////////////
    vector<int> answer;
    for(int i=0;i<bestCombination.size();i++)
    {
        if(bestCombination[i]==1){answer.push_back(i+1);}
    }
    return answer;
}

 

분명 더 효율적으로 짤 수 있는 방법들이 있다

일단은 다른게 급해서 여기까지 ㅠㅠ