Programmers - 스티커 모으기 with JAVA

 

 

문제

원형으로 된 스티커판이 있고 각 스티커판에는 점수가 적혀있다. 하지만 한 스티커를 뗀다면 양쪽 두 스티커는 뗄수 없다. 이 때, 스티커를 뽑아 만들 수 있는 최대값을 구하라.

 

 

 

로직

이 문제는 프로그래머스의 도둑질과 거의 똑같은 문제이다. 사실 값들만 다르고 같은 로직을 사용한다.

하지만 기억이 나지 않았고 기억을 위해 기록해 외워 두려고 한다.

 

1. 두 배열 생성

1-1. Arrays.copyOfRange(array, 0, len-2);

1-2. Arrays.copyOfRange(array, 1, len-1);

 

2. 두 배열 합치기

int[][] list = {list1, list2};

 

3. 배열마다 확인하며 dp처리

 

4. 각 배열마다 마지막 값들 중 최대값이 정답

 

 

코드

import java.util.*;
class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        int len = sticker.length;
        if(len <= 1){
            return sticker[0];
        }
        if(len <= 2){
            answer = Math.max(sticker[0], sticker[1]);
            return answer;
        }
        int[] check1 = Arrays.copyOfRange(sticker, 0, len-1);
        int[] check2 = Arrays.copyOfRange(sticker, 1, len);
        int[][] check = {check1, check2};
        for(int[] now : check){
            int[] dp = new int[len-1];
            dp[0] = now[0];
            dp[1] = Math.max(now[1], dp[0]);
            for(int i=2; i<len-1; i++){
                dp[i] = Math.max(now[i]+dp[i-2], dp[i-1]);
            }
            answer = Math.max(answer, dp[len-2]);
        }
        return answer;
    }
}

 

import java.util.*;
class Solution {
    public int solution(int sticker[]) {
        int answer = 0;
        int length = sticker.length;
        if(length == 1){
            return sticker[0];
        }
        if(length == 2){
            return Math.max(sticker[0], sticker[1]);
        }
        int[] arrayA = Arrays.copyOfRange(sticker, 0, length-1);
        int[] dpA = new int[length-1];
        dpA[0] = arrayA[0];
        dpA[1] = Math.max(arrayA[1], dpA[0]);
        for(int i=2; i<length-1; i++){
            dpA[i] = Math.max(dpA[i-1], dpA[i-2]+arrayA[i]);
        }
        int[] arrayB = Arrays.copyOfRange(sticker, 1, length);
        int[] dpB = new int[length-1];
        dpB[0] = arrayB[0];
        dpB[1] = Math.max(arrayB[1], dpB[0]);
        for(int i=2; i<length-1; i++){
            dpB[i] = Math.max(dpB[i-1], dpB[i-2]+arrayB[i]);
        }
        return Math.max(dpA[length-2], dpB[length-2]);
    }
}