740. Delete and Earn

문제 설명

정수형 배열 nums가 있다. 임의의 원소 nums[i]를 골라 포인트를 얻고 삭제하면 모든 nums[i]+1와 모든 nums[i]-1의 값을 갖는 원소를 삭제해야한다. 이를 이용하여 포인트의 최대값을 구하시오
단, 1 <= nums.length <= 2 * 104 , 1 <= nums[i] <= 104 이다.

출력 예시

접근 방법

첫 시도

정렬된 벡터 배열과 visited배열을 이용하여 반복문 실행.
But 최대값을 찾기 위해 pick하지 않은 원소를 모두 다 pick해야함

두번째 시도

Queue를 이용해서 연속적인 수가 나오면 맨 뒤로 보냄. 원소가 비어있을 때까지 반복
-[1,1,1,2,4,5,5,5,6] 의 경우, 1,1,1 이후 반드시 4를 택하기 때문에 5,5,5를 고르는게 불가능해짐.

세번째 시도

중복되는 원소를 모두 합친 배열 added_nums 생성,인덱스는 원소를 의미.
ex) [1,1,2,2,2,4,5] -> added_nums={0,2,6,0,4,5}
이후 반복문을 이용하여
n번째까지 더한 합의 최대값 = max(n-2번째,n-3번째)+added_nums[n]
result_nums={0,2,6,2,10,11}이므로 출력값은 11이 된다.

소스코드

int deleteAndEarn(vector<int>& nums) {
        int result=0;
        int added_nums[10002]={0};
        int answer[10002]={0};
        sort(nums.begin(),nums.end());
        for(int i=0; i<nums.size(); i++){
            added_nums[nums[i]]+=nums[i];
        }
        
        if(nums.size()==1) return nums[0];
        else if(nums.size()==2) {
            if(nums[0]!=nums[1]-1) return nums[0]+nums[1];
            else return added_nums[nums[1]];
        }
        else{
            int start=nums.front();
            int end=nums.back();
            if(end-start > 1){ 
                answer[start] = added_nums[start];
                answer[start+1] =added_nums[start+1];
                answer[start+2] = answer[start]+added_nums[start+2];

                for(int j=start+3; j<=end; j++){
                    answer[j]=max(answer[j-2],answer[j-3])+added_nums[j];
                }

                result=max(answer[end],answer[end-1]);

                return result;  
            }
            else if(end-start == 1){
                return max(added_nums[start],added_nums[end]);
            }
            else return added_nums[start];
        }          

돌아보기

예외상황을 너무 많이 체크하느라 코드가 더러워짐 ...
다시 공부하고 풀어보자. house robber 문제 참고하기