(C++) - 백준(BOJ) 2303번 : 숫자 게임

www.acmicpc.net/problem/2303

2303번: 숫자 게임

dfs 혹은 backtracking하며 brute force하는 문제였습니다.

 

 

풀이방법

 1. 한 사람마다 5개의 카드를 입력 받은 후 3개의 숫자카드를 dfs로 뽑습니다. 뽑은 후에는 가장 일의자리가 큰 값을 return합니다.

 

 2. 가장 큰 카드의 값, 사람번호 를 pair로 하여 vector에 push 합니다.

 3. 가장 큰 카드의 값이 vector의 처음으로 오도록 내림차순, 그리고 만약 카드의 값이 같다면 사람번호가 오름차순이 되도록 정렬합니다.

 4. 0번째에 있는 사람의 번호를 출력합니다.

 

 

 

 

Code

#include <bits/stdc++.h>
using namespace std;
int cardPerPerson[1000][5], peopleNum;
vector <pair<int,int>> maxCard;
vector <int> cards;
int getMaxCardNum(int curPeople, int depth, int idx, int cardNum){
    if(depth == 3){
        int sum = 0;
        for(int i = 0; i < 3; i++)
            sum += cards[i];
        return max(sum%10,cardNum);
    }
    int maxCardNum = 0;
    for(int i = idx; i < 5; i++){
        cards.push_back(cardPerPerson[curPeople][i]);
        maxCardNum = max(maxCardNum,getMaxCardNum(curPeople, depth+1, i+1, cardNum));
        cards.pop_back();
    }
    return maxCardNum;
}

int main(){
    cin >> peopleNum;
    for(int i = 0; i < peopleNum; i++){
        for(int j = 0; j < 5; j++)
            cin >> cardPerPerson[i][j];
        maxCard.push_back({getMaxCardNum(i,0,0,0) , i + 1});
    }
    sort(maxCard.rbegin(),maxCard.rend());
    cout << maxCard[0].second;
}