[프로그래머스 - Java] 스티커 모으기(2)

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

코딩테스트 연습 - 스티커 모으기(2)

 

풀이

 

처음엔 dfs를 사용해서 재귀로 출려고 생각을 했습니다ㅠㅠ 그러나 처참한 시간초과가 예상되어서 dp로 노선변경

dp[2][len]인 2차원 배열을 사용하였는데요, dp[0][]은 첫번째 스티커를 사용하는 경우를 저장하고 dp[1][]은 첫번째 스티커를 사용하지 않는 경우를 저장합니다.

 

첫번째 스티커 사용O : dp[0][0] = sticker[0], dp[0][1] = sticker[0]

첫번째 스티커 사용X : dp[1][0] = 0, dp[1][1] = sticker[1]

 

dp[][2]부터는 이를 이용해서 max(dp[][i-2]+sticker[i], dp[][i-1])로 구해나가면 됩니다.

이때 중요한 것은 배열의 크기가 1 또는 2인 경우 처리해줘야 한다는 것!!

 

class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        int len = sticker.length;
        
        //스티커 하나 or 두개인 경우 처리
        if(len == 1)
            return sticker[0];
        else if(len == 2)
            return Math.max(sticker[0], sticker[1]);
        int[][] dp = new int[2][len];
        
        dp[0][0] = sticker[0];
        dp[0][1] = dp[0][0];    //첫번째 스티커 사용O
        dp[1][0] = 0;
        dp[1][1] = sticker[1];  //첫번째 스티커 사용X
        
        for(int i=2; i< len-1; i++){
            dp[0][i] = Math.max(dp[0][i-2]+sticker[i], dp[0][i-1]);
            dp[1][i] = Math.max(dp[1][i-2]+sticker[i], dp[1][i-1]);
        }
        
        //첫번째 스티커 안썼으니까 마지막 가능
        dp[1][len-1] = Math.max(dp[1][len-3]+sticker[len-1], dp[1][len-2]);
        answer = Math.max(dp[0][len-2], dp[1][len-1]);
        
        return answer;
    }
}