문제 링크

프로그래머스 문제

풀이

제한조건의 범위가 너무 크고, 효율성테스트를 동시에 겸하고 있기 때문에
완전탐색이 아닐것이라는 생각을 먼저 하게 되었다.
그렇다면 가장 합리적인 알고리즘은 dp 알고리즘이었다.
크게 두가지 경우의 수로 나누게 된다.

1. 첫번째 스티커를 제거한다.
2. 첫번째 스티커를 제거하지 않는다.

코드

function solution(sticker) {
    var answer = 0;
    // 스티거가 하나뿐인경우
    if(sticker.length === 1) return sticker[0]
    // 여기 이후로부터는 적어도 스티커가 2개 이상인것을 보장함
    // 첫번째를 사용하는 경우
    const useFirst = new Array(sticker.length-1).fill(0)
    useFirst[0] = sticker[0]
    useFirst[1] = useFirst[0]
    
    for(let i=2; i < useFirst.length; i++){
        useFirst[i] = Math.max(useFirst[i-2] + sticker[i] , useFirst[i-1])
    }
    
    // 첫번째를 사용하지 않는 경우 
    const notUseFirst = new Array(sticker.length).fill(0)
    notUseFirst[0] = 0;
    notUseFirst[1] = sticker[1] 
    
    for(let i=2; i < notUseFirst.length; i++){
        notUseFirst[i] = Math.max(notUseFirst[i-2] + sticker[i] , notUseFirst[i-1])
    }
    
    return Math.max(notUseFirst.pop() , useFirst.pop());
}