(코테) 프로그래머스_스티커 모으기(2) *DP

 

문제링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/12971?language=java

 

 

 

 

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        int len = sticker.length;   
        if (len == 1) return sticker[0];
        if (len == 2) return Math.max(sticker[0], sticker[1]);
        
        
        int case1 = loop(sticker,0,len-2);
        int case2 = loop(sticker,1,len-1);
        
        answer = Math.max(case1,case2);
        
        
        return answer;
    }
    public int loop(int[] sticker,int start,int end){
            int prev1=0;
            int prev2=0;    
        
        for(int i=start;i<=end;i++){
            int take = prev2+ sticker[i];            
            int cur = Math.max(prev1,take);
            prev2=prev1;
            prev1=cur;                        
        }
        return prev1;             
    }
}

 

 

회고.

 

1.문제 접근 방식

문제 유형을 파악할때 우선 최선의 선택지들의 합으로 최대값을 찾는 그리디 ,완전탐색,DP 정도 생각이 들었다.

하지만 완전탐색(백트레킹)은 시간초과로 절대 적합하지 않을거라 판단했고, 

그리디, DP 정도로 좁혔다. 

각 배열의 인덱스마다 최상의 값을 기억해두고 푸는게 적합하다고 생각했다.  그래서 DP가 더 맞을거 같다고 생각했는데 

코딩을 어떻게 시작해야할지 조금 어렵게 느껴졌다. 

 

2. 예외처리

문제에서 첫 인덱스와 마지막 인덱스가 서로 연결된다라는 전제를 주었다. 

그래서 첫 인덱스- (마지막인덱스-1)   , 두번쨰 인덱스 - 마지막인덱스  로 두 번 나눠서 빠짐 없이 순회되게 

처리하는 방법을 확인하였다. 

 

3. 순회법

숫자를 뽑을때 -1,1 두개 인덱스 배열들은 손상을 입어 사용을 못한다. 

prev1 , prev2 를 두어 -2 배열의 최상위값  -1 배열의 최상위 값을 저장해두며 

-2배열의 최상위값과 현재 배열의 값을 더한값  과    -1배열의 최상위 값을 비교하며  값을 갱신시켜준다.  

(prev2 +arr[i])  <-> prev1  두 값 중 더 큰 값을 최상위 값으로 채택  (prev1은 항상 최상위 값을 갱신시켜준다. )

prev2는 이전 prev1을 넣어주고. (최상위로 갱신되기 전의 prev1값을 넣어줌.)