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

문제 설명

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

 

---

 

제한 사항

 

---

 

입출력 예

 

---

 

풀이

class Solution {
    public int solution(int sticker[]) {
        if (sticker.length == 1) return sticker[0];
        else if (sticker.length == 2) return Math.max(sticker[0], sticker[1]);
        
        int[] result0 = new int[sticker.length];
        int[] result1 = new int[sticker.length];
        
        result0[0] = sticker[0];
        if (sticker.length > 3) result0[2] = result0[0] + sticker[2];
        for (int i = 3; i < sticker.length - 1; i++) {
            result0[i] = Math.max(result0[i - 2], result0[i - 3]) + sticker[i];
        }
        
        result1[1] = sticker[1];
        result1[2] = sticker[2];
        for (int i = 3; i < sticker.length; i++) {
            result1[i] = Math.max(result1[i - 2], result1[i - 3]) + sticker[i];
        }
        
        return Math.max(
            Math.max(result0[result0.length - 3], result0[result0.length - 2]),
            Math.max(result1[result1.length - 2], result1[result1.length - 1]));
    }
}

 

---

 

후기

처음에 BFS나 DFS로 접근해보려고 했는데 생각해 보니 그렇게 하면 경우의 수가 너무 많아져서 포기했다.

좀 더 생각해 보니 DP로 이전의 최댓값을 저장하는 방식으로 접근하면 어떨까 해서 그렇게 풀었는데 다행히 통과했다.

사실 이거 이전에 Set으로 다음 인덱스를 저장하며 총 3번 순회하는 반복문을 작성했는데 통과는 되지만 효율성 테스트에서 너무 오래 걸려서 다시 생각했다...

 

접근법은 숫자가 원형 띠 형태로 이루어져 있다고 했으니 일단 시작점을 정해야 한다.

그런데 숫자들이 배열로 주어지니 시작점은 배열의 시작점으로 잡는 것이 편하다.

한 숫자를 선택할 때, 양 옆의 숫자는 사용하지 못하니 첫 번째 배열의 요소를 선택하면 마지막 배열의 요소를 선택하지 못한다. 그래서 범위는 0 ~ stickers.length - 2 까지만 접근할 수 있다.

만약 첫 번째 요소를 선택하지 않는다면 배열의 인덱스는 1부터 시작한다. 1 ~ stickers.length - 1 까지가 이에 해당한다.

 

범위를 정했으면 이제 어떻게 최대값을 누적하며 진행할까 고민해야 한다.

숫자를 선택하는 방법은 크게 두 가지가 있다.

 

2칸 떨어진 숫자 선택, 3칸 떨어진 숫자 선택

 

2칸 앞, 3칸 앞의 인덱스의 값을 가져와서 현재 인덱스의 값과 더한 것 중 더 큰 것을 자신의 값으로 저장하면 된다.

 

사실 처음에 반대로 2, 3칸 뒤로 접근했는데 이렇게 하면 마지막 배열 범위에 맞춰서 처리하기가 쉽지 않아서 그냥 2, 3칸 전으로 구현했다. 이렇게 하면 시작점에서만 처리를 잘해주면 배열 끝 부분은 고민할 필요 없다.

 

4칸 뒤 부터는 2, 3칸의 반복이므로 이미 고려한 부분을 추가로 고려하는 거라 의미가 없다.

그래서 2, 3칸 건너뛰는 경우만 고려하면 된다.

 

 

문제를 보니까 전에 풀었던 문제랑 비슷해서 찾아보니까 작년에 풀었던 문제랑 비슷했다.

 

https://megamaker.tistory.com/153

[프로그래머스][JAVA][Lv. 4] 도둑질