프로그래머스 - 스티커 모으기 (DP , 점화식)

프로그래머스

 

 

이번 문제는 처음 보는 유형의 문제로, 검색 엔진으로 풀이 방식을 찾아서 해법을 찾아야 했다.
처음 보는 유형의 문제였고, 검색을 통해 확인한 결과 DP를 사용하여, 점화식을 세워서 푸는 문제이다.

 

 

 

---

public int solution(int[] sticker)
{
    int n = sticker.Length;
    if (n == 1) return sticker[0];

    // 1. 첫 번째 스티커 선택
    int[] dp1 = new int[n];
    dp1[0] = sticker[0];
    dp1[1] = Math.Max(sticker[0], sticker[1]);
    for (int i = 2; i < n - 1; i++)
    {
        dp1[i] = Math.Max(dp1[i - 1], dp1[i - 2] + sticker[i]);
    }

    // 2. 첫 번째 스티커 선택하지 않음
    int[] dp2 = new int[n];
    dp2[0] = 0;
    dp2[1] = sticker[1];
    for (int i = 2; i < n; i++)
    {
        dp2[i] = Math.Max(dp2[i - 1], dp2[i - 2] + sticker[i]);
    }

    return Math.Max(dp1[n - 2], dp2[n - 1]);
}

 

 

이런 식으로 답이 나오며,
이때 핵심은 첫 번째를 선택하거나 첫 번째를 선택하지 않거나로 분기가 나뉘게 된다는 점을 체크해
추후 두 값을 비교하는 것으로 풀어내는 방식이다

점화식은 DP [i] = max(DP [i-1], DP [i-2] + sticker [i]) 형식으로,
하나를 택하면 앞 뒤의 스티커를 선택하지 못하기에 어느쪽의 합이 더 큰지를 확인하는 점화식 구조를 가진다.