[프로그래머스] 스티커 모으기(2) Java 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/12971

프로그래머스

 

풀이 방법

DP를 사용해서 푼다.

첫번째 스티커를 뗀 경우와 안 뗀 경우의 배열을 나눠서 푼다.

 

dp[i] : i번째 까지의 최댓값

 

첫번째 스티커를 뗀 배열 dp라면

dp[0]의 값은 첫번째 스티커를 뗀 값이므로 sticker[0]

dp[1]의 값은 첫번째 스티커를 뗀 경우 index 1의 위치에서는 스티커를 뗄 수 없으므로 1의 앞 index인 0의 값이 최대가 된다.

 

첫번째 스티커를 떼지 않은 배열 dp2라면

dp2[0]의 값은 첫번째 스티커를 뗄 수 없으므로 0의 위치까지의 최댓값은 0이 된다.

dp2[1]의 값은 첫번째 스티커를 떼지 않았으니 1의 위치까지의 최댓값은 1의 스티커를 뗀 값이 된다.

 

첫번째 스티커를 떼거나 떼지 않은 경우 모두 둘다

index 2이상에서부터는 다음 규칙을 적용 받는다.

dp[i] = max( dp[i-2], + sticker[i], dp[i-1] )

• dp[i-2] + sticker[i] : i-2 위치까지의 최댓값에 i 위치 스티커를 떼는 경우
• dp[i-1] : i 위치의 스티커를 떼지 않으므로 i-1 까지의 최댓값

둘중 최댓값을 i번째의 값으로하면 된다.

 

dp의 경우

마지막 스티커는 뗄 수 없음을 주의해서 반복문을 돌린다.

최종 최댓값은 마지막 인덱스의 앞에 존재하게 된다.

 

dp2의 경우

마지막 스티커까지 떼므로 반복문을 끝까지 돌린다.

최종 최댓값은 마지막 인덱스에 존재하게 된다.

 

전체 코드

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        int dp[] = new int[100000]; // 첫번째 스티커를 뗀 경우
        int dp2[] = new int[100000]; // 안뗀 경우
        dp[0] = sticker[0];
        dp2[0] = 0;
        
        if(sticker.length > 1) {
            dp[1] = sticker[0];//첫번째 스티커를 뗀 경우 dp[1]은 idx 1을 뗼 수 없으니 idx 0의 값이다.
            dp2[1] = sticker[1];//첫번째 스티커를 안 뗀 경우 dp2[1]은 idx 1의 스티커를 뗀 값이 최대이다.
        } else {
            return sticker[0];
        }
            
        
        // dp[i] 위치의 값은
        // i 위치의 스티커를 뗀다면
        // i-1번째 스티커를 떼지 않은걸 뜻하는 dp[i-2] 값에 sticker[i] 값을 더한것
        // 또는
        // i 위치의 스티커를 떼지 않는다면
        // dp2[i-1]의 값이 그대로 넘어온다.
        
        for(int i=2; i<sticker.length-1; i++) {
            dp[i] = Math.max(dp[i-2] + sticker[i], dp[i-1]);
        }
        
        for(int i=2; i<sticker.length; i++) {
            dp2[i] = Math.max(dp2[i-2] + sticker[i], dp2[i-1]);
        }
        
        // sticker.length-2 < 0인 경우는 return sticker[0];에서 걸러짐
        answer = Math.max(dp[sticker.length-2], dp2[sticker.length-1]);
        return answer;
    }
}