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

1. 문제

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

프로그래머스

2. 코드

해당 문제는 앞의 값을 저장해가는 누적합을 사용해야 하기 때문에 DP가 사용된다.

총 두 가지 경우가 있고, 이 두 가지 경우를 분기처리 하여 누적합을 구해준 뒤 최댓값을 산출해주면 된다.

• 첫번째 스티커 떼고 시작하는 경우(마지막 스티커 사용 못하고 끝남)
• 첫번째 스티커 떼지 않고 시작하는 경우(마지막 스티커 사용하고 끝남)

총 두 가지 경우를 나누어, 이전 스티커를 떼었을 경우와 이전 스티커를 떼지 않아 현재 스티커를 뗄 수 있는 경우의 최댓값을 구해 더해가면 된다.

function solution(sticker) {
  const len = sticker.length + 2; // i-2 요소 값을 구해야하기 때문
  const dp1 = new Array(len).fill(0); // 첫번째 스티커 뜯은 경우
  const dp2 = new Array(len).fill(0); // 첫번째 스티커 뜯지 않은 경우
  
  if(sticker.length === 1) return sticker[0]; // 스티커가 하나 일 때
  
  // 첫번째 스티커 뜯고 시작하는 경우
  for(let i = 2; i < len-1; i++)
    // 이전의 스티커를 뜯어 지금 스티커를 뜯을 수 없는 경우(지금까지의 합)
    // 이전의 스티커를 뜯지 않아 지금 스티커를 뜯을 수 있는 경우(지금까지의 합 + 현재 스티커 값)
    dp1[i] = Math.max(dp1[i-1], dp1[i-2] + sticker[i-2]); 
   // 첫번째 스티커 뜯지 않고 시작하는 경우
  for(let i = 3; i < len; i++) 
    dp2[i] = Math.max(dp2[i-1], dp2[i-2] + sticker[i-2]);
  
  return Math.max(dp1[len-2], dp2[len-1]); // 첫번째 뜯은 경우의 len-2에, 뜯지 않은 경우는 len-1에 최댓값 있음
}

 

이해에 참고한 블로그)

https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EC%8A%A4%ED%8B%B0%EC%BB%A4-%EB%AA%A8%EC%9C%BC%EA%B8%B0-JS

[프로그래머스] LV.3 스티커 모으기 (JS)

 

어렵다!! 이건 많이 풀어보는게 답인 듯 하다...그래 bfs,dfs 때도 이랬잖아! 할 수 있다!!!!

그래도 DP, 투포인터 너어어무 어렵다 ㅠㅠㅠ

 

복기

6/28