백준 2303. 숫자 게임

https://www.acmicpc.net/problem/2303

2303번: 숫자 게임

 

하 ..

요즘 한창 재귀 함수 만드는것을 연습하고 있는데 오늘 잘되지도않고

문제도 더럽게 안풀려서 마지막으로 쉬운거 하나 풀고 쉬려고 난이도 실버5 짜리를 골라서 풀었다.

딱 봐도 그냥 5개중 3개 조합 골라서 쉽게 풀수 있을줄 알았는데 

 

 

중간에 배열들도 다 출력해보고 아무리 확인해봐도 맞은것 같은데 계속 틀리다고 나와서 때려치고 내일할까 ..

한번만 더해보자 이러다가 거의 한시간을 날렸다.

 

결국 답을 찾았는데 중간에 배열 사이즈를 최댓값인 1000 이상으로 만들었어야 하는데

문제에서 주어진 n=3인 예시를 생각하며 풀다가 크기를 3으로 만들어서 계속 틀렸던 것이었다.

 

문제 자체는

permutation 함수로 5개중 3개 조합을 뽑는 방식으로 쉽게 풀수있다.

오늘은 이제 좀 쉬고 내일 재귀를 이용한 dfs 방식으로 한번만 더 풀어봐야겠다.

 

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

int n;
int cards[1001][5];
int mark[5] = {1, 1, 1, 0, 0};
// 각 사람들이 낼수 있는 최대값이 저장됨
int maxs[1001];


int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            cin >> cards[i][j];
        }
    }


    do {

        for(int a = 0; a < n; a++)
        {
            int sum[1001] = {0,};

            for(int i = 0; i < 5; i++)
            {
                if(mark[i] == 1)
                    sum[a] += cards[a][i];
            }

            maxs[a] = max(maxs[a], sum[a] % 10);
            
        }

    } while(prev_permutation(mark, mark+5));


    int winner = 0;
    int highest = maxs[0];
    for(int i = 1; i < n; i++)
    {
        if(maxs[i] >= highest)
        {
            winner = i;
            highest = maxs[i];
        }
    }

    cout << winner+1;
}