[프로그래머스/C++] 주사위 고르기 (2024 KAKAO WINTER INTERNSHIP)

 

 

문제

문제 설명

 

  

 

풀이

 

[문제 풀이]

 

처음에 주사위 숫자를 잘 사용하면 전부 비교하지 않아도 풀리지 않을까? 했는데, 그냥 비교하는게 맞는 풀이였다...

 

A가 주사위를 선택하면 B는 남은 주사위를 갖는다.

이후 A가 선택한 주사위로 만들 수 있는 모든 경우를 구한다.

(제한에 따르면 약 2 * 10C5 * 6^5 이므로 가능하다고 판단했다.)

 

이후 선택된 주사위에서 A와 B에서 나올 수 있는 모든 주사위의 합이 구해지면, 정렬을 한다.

 

정렬을 한 다음 A와 B를 비교하고 만약 A가 크면 B의 idx를 +1 한다.

만약 B가 A보다 크거나 같으면 이긴 경우의 수에 B의 idx를 더하고 A의 idx를 1 더한다.

 

예를 들어 아래와 같이 구해졌다면,

 7과 4를 비교하고 다음에 비교할 b의 idx를 1 높인다.

다음번에 7과 7을 비교한 결과 B가 크거나 같으므로 b의 idx(A가 이긴 경우의 수)를 이긴 횟수에 더하고, A의 idx를 1 높인다.

 

위 과정을 반복하면 n^2비교할 필요 없이 최대 2*n번 비교하면 된다.

 

​

[아이디어 정리]

1. 주사위를 선택하는 경우의 수를 전부 구한다.​
2. 선택한 주사위를 바탕으로 나올 수 있는 주사위 눈 합의 경우의 수를 전부 구한다.
3. 주사위 눈의 합들을 정렬하고, 비교를 통해 이길 수 있는 횟수를 계산한다.
4. 이 중에서 가장 이길 수 있는 횟수가 많은 경우를 return한다. 

 

Code

 

 

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

int targetDiceNum;
vector<vector<int>> realDice;
vector<int> DiceListA;
vector<int> DiceListB;
int maxWinNum;
vector<int> winA;

void makeList(vector<int> DL,bool isA, int deep, int Num) //주사위 조합 구하기
{
    if (deep==DL.size())
    {
        if (isA)
        {
            DiceListA.push_back(Num);
        }
        else
        {
            DiceListB.push_back(Num);
        }
        return;    
    }
    else
    {
        for (int i=0; i<6; i++)
        {
            makeList(DL, isA, deep+1,Num+realDice[DL[deep]][i]);
        }
    }
}

void calc(vector<int> AD,vector<int> BD)
{
    DiceListA=vector<int>(0);
    DiceListB=vector<int>(0);
    makeList(AD, true, 0, 0);
    makeList(BD, false, 0, 0);
    sort(DiceListA.begin(),DiceListA.end());
    sort(DiceListB.begin(),DiceListB.end());
    int aIdx=0, bIdx=0;
    int winNum=0;
    while (aIdx<DiceListA.size()&&bIdx<DiceListB.size()) //주사위 합 비교
    {
        if (DiceListA[aIdx]>DiceListB[bIdx])
        {
            bIdx+=1;
        }
        else
        {    
            winNum+=bIdx;
            aIdx+=1;
        }
    }    
    if (bIdx==DiceListB.size())
    {
        winNum+=bIdx*(DiceListA.size()-aIdx);
    }
    if (winNum>maxWinNum)
    {
        maxWinNum=winNum;
        winA=AD;
    }
}

void combi(vector<int> AD,vector<int> BD, int nowD)
{
    vector<int> tD;
    if (AD.size()==targetDiceNum)
    {
        tD=BD;
        for (int i=nowD; i<realDice.size(); i++)
        {
            tD.push_back(i);
        }
        calc(AD,tD);
    }
    else if (BD.size()==targetDiceNum)
    {
        tD=AD;
        for (int i=nowD; i<realDice.size(); i++)
        {
            tD.push_back(i);
        }
        calc(tD,BD);
    }
    else
    {
        tD=AD;
        tD.push_back(nowD);
        combi(tD, BD, nowD+1);
        tD=BD;
        tD.push_back(nowD);
        combi(AD, tD, nowD+1);
    }
    return;
}

vector<int> solution(vector<vector<int>> dice) {
    realDice=dice;
    targetDiceNum=dice.size()/2;
    combi(vector<int>(0),vector<int>(0), 0);
    for (int i=0; i<winA.size(); i++)
    {
        winA[i]+=1;
    }
    return winA;
}

 

---

 

조합을 구현하다보니 코드가 많이 길어졌다...

그리고 조합을 만들면서 vector를 복사해 전달하는 부분에서 좀 효율성이 떨어지는 것 같은데 나중에 어떻게 고칠까 고민해 봐야겠다.

 

 

프로그래머스