🔎 스티커 모으기(2)
❓ 문제링크
https://programmers.co.kr/learn/courses/30/lessons/12971
📄 제출 코드
function solution(sticker) {
const len = sticker.length+2;
const dp1 = new Array(len).fill(0);
const dp2 = new Array(len).fill(0);
if (len-2 == 1) return sticker[0];
for (let i = 2; i < len; i++) {
// console.log(`dp1[i-1] : ${dp1[i - 1]}, dp1[i-2] : ${dp1[i - 2]}, sticker[i - 2]: ${sticker[i-2]}`);
dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + sticker[i - 2]);
// console.log(`dp1[i] : ${dp1[i]}`);
}
for (let i = 3; i < len; i++) {
dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + sticker[i - 2]);
// console.log(`dp2[i] : ${dp2[i]}`);
}
// console.log(dp1);
// console.log(dp2);
return Math.max(dp1[len-2], dp2[len - 1]);
}
let sticker = [14, 6, 5, 11, 3, 9, 2, 10];
console.log(solution(sticker));처음에는 어떤 규칙이 있는 배열문제라고 생각 하고 풀었다.
배열로 풀때는 그냥 짝수번째 시작인경우와 홀수번째 시작인 경우로 한칸씩 건너뛰면서 요소들을 합쳐 최대값을 구하려고했는데 진행하다가 의문이 들었다. 1번째 3번째를 선택하고 5가아니라 6을 선택하는 경우도 생길 수 있단 생각이들어 고민하게 되었다.
결국 풀지 못하였고, 다른 사람의 해설을 보게 되었다.
이 문제는 DP로 접근해야 하는 문제이다.
현재 뜯은 스티커 + 다음 뜯을 스티커의 누적 합이 최대값이 되는 경우를 찾아야한다.
주의 할 점은 인접한 스티커는 뜯을 수 없고, 처음과 끝이 연결되있는 형태로 생각해야한다.
각 dp배열에는 해당 번째까지 뜯었을 때의 최대값을 저장할 것이다.
첫 번째를 뜯는다고 생각할 경우 3번째 부터 뜯을 수 있고 3번째를 뜯을지 4번째를 뜯을지에 따라 누적합이 달라진다.
첫 번째를 뜯지 않는다고 생각하면, 두 번째에서 마지막까지 뜯을 수 있다.
우리가 만들 식은 다음과 같다.
dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + sticker[i - 2]);i번째를 뜯으려고 할 때, 이전까지 뜯었을 때 최대값과 두칸 전 스티커와 현재값을 뜯은것의 합을 비교하여 최대값을 저장한다.
(sticker[i-2]인 이유는 i-2의 값을 구하기 위해 초기 배열을 +2했기 때문에 현재 더해볼 스티커의 인덱스는 i-2가 되야한다.)
모든 반복이 끝나면 dp1의 경우 시작점부터 뜯었으니 dp[len-2]가 정답이 될것이고, dp2의 경우 첫 번째를 뜯지 않아 마지막 인덱스는 len-1이 될 것이다.
아직은 어떤 문제가 DP인지 눈에 바로 보이지 않고, 어떻게 점화식을 만들어서 풀어나가는지 공부가 부족한거 같다. 더 열심히 해야겠다.
📘 참고
