프로그래머스 - 스티커 모으기(2) (Java, 자바)

문제 링크

문제 설명

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로 최대가 됩니다.

---

문제 풀이 방법

처음에 이 문제를 접했을 때 짝수, 홀수 인덱스 값들을 전부 더하는 방식으로 풀었는데 이건 옳은 방법이 아니라는 것을 알았다.
이 문제 또한 DP 방법으로 문제를 풀이 해야한다.

이 문제는 두가지 경우를 생각해서 풀이 해야한다.
첫번째 스티커를 선택했을 때와 첫번째 스티커를 선택하지 않고 두번째 스티커부터 선택했을때 두가지를 구한 다음 최댓값을 구하면 된다.

우선 첫번째 스티커를 선택 했을 때를 보자.

첫번째 스티커를 선택 했을 때 첫번째 값은 그대로 14가 되며, 2번째 스티커는 선택이 불가하므로 이전 값인 14가 된다.

3번째 스티커를 사용할때 바로 앞에 있는 스티커는 사용이 불가하므로 -2 위치인 1번 위치의 스티커와 현재 위치의 값을 더한다.
여기서 현재 위치 값을 사용하지 않으면 바로 앞에 스티커를 사용 할수 있으므로 앞에 값과 비교하여 큰 값을 선택 한다.

이것을 배열 끝까지 반복하면 된다.

단 첫번째 스티커를 선택했으니 마지막 스티커 선택이 불가하다.
따라서 첫번째 스티커를 선택 했을 때의 최댓값은 34가 된다.

 

이제 두번째 스티커 선택 했을 경우를 보자.

두번째 스티커를 선택 했을때는 첫번째 스티커를 선택 못하니 첫번째 값은 0이 되고, 두번째 값은 6이 된다.

3번째 스티커를 사용할때 바로 앞에 있는 스티커는 사용이 불가하므로 -2 위치인 1번 위치의 스티커와 현재 위치의 값을 더한다.
여기서 현재 위치 값을 사용하지 않으면 바로 앞에 스티커를 사용 할수 있으므로 앞에 값과 비교하여 큰 값을 선택 한다.

두번째 스티커를 선택 했을 때는 마지막 인덱스 값을 선택이 가능하니 끝까지 반복하여 진행 한다. 이때 최댓값은 36이 된다.

 

첫번째 스티커를 선택 했을 때 34, 두번째 스티커를 선택했을 때 36이 되며 이중 큰 값은 두번째 스티커를 선택 했을 때인 36이 된다.

 

이것을 코드로 표현하면 dp[i] = Math.max(dp1[i - 1],dp1[i - 2] + sticker[i]) 이 된다.

---

전체 코드

class Solution {
    public int solution(int sticker[]) {
        if (sticker.length == 1) {
            return sticker[0];
        }

        int[] dp1 = new int[sticker.length];
        int[] dp2 = new int[sticker.length];

        dp1[0] = sticker[0];
        dp1[1] = sticker[0];
        for (int i = 2; i < sticker.length - 1;i++) {
            dp1[i] = Math.max(dp1[i - 1],dp1[i - 2] + sticker[i]);
        }

        dp2[0] = 0;
        dp2[1] = sticker[1];
        for (int i = 2; i < sticker.length; i++) {
            dp2[i] = Math.max(dp2[i - 1],dp2[i - 2] + sticker[i]);
        }

        return Math.max(dp1[sticker.length - 2],dp2[sticker.length - 1]);
    }
}