[JS] 스티커 모으기(2)

문제

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

프로그래머스

 

 

풀이

문제의 첫 인상은 0번 요소와 1번 요소를 선택했을 때 1개씩 건너뛰어 선택한 조합을 구하면 되지 않을까 라는 생각을 했다. 하지만, 이 경우 한개를 건너뛴 선택이 더 클 수 있다고 생각했다.

 

그래서 다른 접근법을 생각해봤다. 우선 문제의 제한 조건을 보고 2중 이상의 for문을 사용한 접근법은 시간복잡도상 초과될 것이라 생각해 DP를 이용해 메모이제이션을 구현해 풀이를 진행했다.

 

문제의 풀이법의 경우 0번 요소를 선택했을 때와 1번 요소를 선택한 경우를 나누어 진행했다. 이렇게 풀이한 이유는 0번을 선택한 경우 맨 뒤의 요소를 선택할 수 없으며, 1번 요소를 선택하면 맨 뒤 요소를 선택할 수 있다. 왜 맨 뒤 요소를 고려해야하나 라는 질문에는 맨 뒤 요소를 선택하고 안하고에 따라 결과가 달라질 수 있기 때문이다 라고 답할 수 있다.

 

사실 이 문제를 풀며 가자 고민했던 것은 이렇게 두가지 경우를 이용해 풀이한다고 해도, 선택한 요소의 좌 우 요소를 사용하면 안되기 때문에 이 동작을 어떻게 구현할까이다. 이는 사실 생각하지 않아도? 된다. 어짜피 맨 뒤의 요소를 선택하고 안하고를 이용해 첫 순간에 0번 요소를 선택하거나 나머지 요소를 선택 하냐를 나누기 때문이다.

 

이후에 DP를 이용한 최대 합을 구할 때 (현제 요소와 이전전 요소의 합)과 이전 요소 중 최대 값을 현재 위치에 넣는다.

 

코드

function solution(sticker) {
  const len = sticker.length;
  const dp1 = Array.from({ length: len - 1 }, () => 0);
  const dp2 = Array.from({ length: len - 1 }, () => 0);
    
  if (sticker.length === 1) return sticker[0];
    
  for (let i = 0; i < len - 1; i++) {
    if (i === 0) dp1[i] = sticker[i];
    else if (i === 1) dp1[i] = Math.max(dp1[i - 1], sticker[i]);
    else {
      dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + sticker[i]);
    }
  }
    
    
  for (let i = 1; i < len; i++) {
    if (i === 1) dp2[i - 1] = sticker[i];
        
    else if (i === 2) dp2[i - 1] = Math.max(dp2[i - 2], sticker[i]);
    else {
      dp2[i - 1] = Math.max(dp2[i - 2], dp2[i - 3] + sticker[i]);
    }
  }
  return Math.max(dp1.at(-1), dp2.at(-1));
}