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

문제 설명

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

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

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

 

제한 사항

• sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.
• sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.
• 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

입출력 예

sticker  /  answer

[14, 6, 5, 11, 3, 9, 2, 10]	36
[1, 3, 2, 5, 4]	8

입출력 예 설명

입출력 예 #1
6, 11, 9, 10이 적힌 스티커를 떼어 냈을 때 36으로 최대가 됩니다.

 

입출력 예 #2
3, 5가 적힌 스티커를 떼어 냈을 때 8로 최대가 됩니다.

 

---

 

풀이

- 계속 삽질하다가 결국 풀이 보고 풀었다.

- 일단 두 가지 경우로 나뉨  : 첫 번째 스티커를 떼는 경우 vs 두 번째 스티커를 떼는 경우

- 각각 다른 배열에 각 인덱스까지의 스티커의 최대 합을 저장함

 

dp1[i] 는 첫 번째 스티커를 뗐을 때 i번째 스티커까지 스티커의 최대 합.

 

따라서

- dp1은 dp1[0] = dp1[1] = sticker[0] 이렇게 초기화해줌 //첫 번째를 떼면 두 번째껄 못 떼니까

- dp2는 첫번째껄 못 떼니까 dp[0] = 0, dp[1] = sticker[1]로 초기화

 

이후에 sticker.length-1까지 반복문을 돌면서

현재 스티커(i)를 dp[i-2]에 더한 값 vs dp[i-1] 값을 비교해서 저장해줌 //dp[i-1]값이 더 크다면 더하지 않고 지나감

 

반복문 다 돌고 나서

dp1은 마지막 두 요소 중 비교해서 큰 값을 최종 값으로 선정하고

dp2는 dp2[i-2]+마지막 스티커 vs dp[i-1] 값을 비교해 선정

 

마지막으로 두 개 비교해서 큰 값 리턴

 

import java.lang.Math;
import java.util.Arrays;

class Solution {
    public int solution(int sticker[]) {
        int size = sticker.length;
    
        if(size <= 3){
            return Arrays.stream(sticker).max().getAsInt();
        }
            
        //각 인덱스까지의 스티커 최대 합을 저장할 배열
        //첫 번째 스티커를 떼는 경우와 두 번째 스티커를 떼는 경우로 나눠서 저장
        int[] dp1 = new int[size];
        int[] dp2 = new int[size];
        
        dp1[0] = dp1[1] = sticker[0];
        dp2[0] = 0; dp2[1] = sticker[1];
        
        for(int i=2; i<size-1; i++){
            //이전에 구한게 더 크면 스티커 떼지 않고 유지
            dp1[i] = Math.max(dp1[i-2]+sticker[i], dp1[i-1]);
            dp2[i] = Math.max(dp2[i-2]+sticker[i], dp2[i-1]);
        }

        int i = size-1;
        dp1[i] = Math.max(dp1[i-1], dp1[i-2]);
        dp2[i] = Math.max(dp2[i-2]+sticker[i], dp2[i-1]);
        
        return Math.max(dp1[i], dp2[i]);
    }
}

 

 

셀프 피드백

- dp 문제 좀 더 많이 풀어봐야 할 듯

- 처음에 첫 번째, 두 번째, 세 번째 떼는 경우라고 생각했는데.. 3번째를 뗄 거면 1번째도 당연히 떼는 거였음..ㅎㅎ 머쓱