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

13 Feb 2024 in Algorithm on 기타

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

풀이

원형으로 된 스티커가 있고, 어느 한 칸을 떼면 양 옆의 칸에 있는 스티커는 뗄 수 없다.

이때, 스티커를 떼어 얻을 수 있는 최댓값을 구하는 문제이다.

배열의 길이가 100,000이기 때문에 dp로 푸는 문제였다.

점화식은 다음과 같다.

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

바로 이전 스티커를 떼었으면 현재 칸을 뗄 수 없고, 현재칸을 떼려면 i-2 칸의 점수에서 더해줘야한다.

다만, 생각해야할 점은 스티커가 원형으로 붙어있기 때문에 첫번째 스티커가 마지막 스티커에 영향을 준다는 것이다.

따라서, 이차원 배열을 만들어 첫번째 스티커를 떼는 경우를 dp[i][1]에 넣고, 떼지 않는 경우를 dp[i][0]에 넣어 진행했다.

---

메모리: 57.9MB

시간: 13.64ms

언어: Java 11

코드

class Solution {
    public int solution(int sticker[]) {
        int len = sticker.length;

        if(len == 1) {
            return sticker[0];
        }

        int[][] dp = new int[len][2];
        dp[0][1] = sticker[0];
        dp[1][1] = dp[0][1];
        dp[1][0] = sticker[1];

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

        return Math.max(dp[len - 1][0], dp[len - 2][1]);
    }
}