프로그래머스 1단계 - 폰켓몬

https://programmers.co.kr/learn/courses/30/lessons/1845#qna

코딩테스트 연습 - 폰켓몬

- 문제 파악

홍박사는 폰켓몬 N 마리를 주어지고, 우리는 그 중의 반만 가져갈 수 있다. 하지만 우리는 다양한 종류의 폰켓몬을 가져가고 싶다. 이 때 가장 많은 종류를 가져가는 경우에 종류의 수를 출력하라.

 

- 정답

재귀함수로 열심히 풀어봤다.

시간초과 발생하는 몇개 케이스 때문에 코드가 조금 억지로 짜여진거 같다.

#include "bits/stdc++.h"
using namespace std;

int nSize;
int arr[200002];
vector<int> numbers;
int answer = 0;

void func(int k, int pos)
{
    if(k == nSize || k == numbers.size())
    {
        answer = max(answer, k);
        return;
    }
        
    if(answer == nSize || answer == numbers.size())
        return;
    
    for(int i = pos ; i < numbers.size() ; i++)
    {
        if(pos + answer >= numbers.size() || i + answer >= numbers.size())
            return;
            
        int a = numbers[i];
        if(!arr[a])
        {
            arr[a] = 1;
            func(k+1, i+1);
            arr[a] = 0;
        }
        
    }
    
}

int solution(vector<int> nums)
{    
    nSize = nums.size()/2;
    
    for(auto a : nums)
    {
        if(!arr[a])        
        {
            numbers.push_back(a);
            arr[a] = 1;
        }
        
    }
    
    fill(arr,arr+200001,0);
    
    func(0,0);
   
    return answer;
}