99클럽 코테 스터디 34일차 TIL - 2944 Minimum Number of Coins for Fruits

2944. Minimum Number of Coins for Fruits / c++ / Medium / 1시간+

문제 및 코드

inline int MIN(int a, int b) {return a < b ? a : b;}

vector<int> dp;

int Calculate(vector<int>& prices, int index)
{
    if (prices.size() <= index) return 0;
    if (dp[index] == -1)
    {
        int minResult = numeric_limits<int>::max();
        int endIndex = index * 2 + 2;
        for (int i = index + 1; i <= endIndex; ++i)
        {
            minResult = MIN(minResult, Calculate(prices, i));
        }
        dp[index] = prices[index] + minResult;
    }

    return dp[index];
}

class Solution {
public:
    int minimumCoins(vector<int>& prices) {
        dp = vector<int>(prices.size(), -1);

        return Calculate(prices, 0);
    }
};

접근 방식

동적 계획법

1. i번째 과일을 사면, 그 이후의 i + 1 개만큼의 과일을 무료로 받을 수 있을 때, 모든 과일을 사는 최소 가격을 반환하는 문제
2. 현재 과일을 사는 것, 사지 않는 것 (이전에 과일을 산 경우) 로 나뉘어 풀리게 되므로 분할 정복, 그 중에서도 이전 값을 활용할 수 있으므로 DP를 사용했다.
3. 계산식은, i번째 과일의 가격 + (2 * i + 2) 번째까지 중 가장 작은 값이 된다.
   (여기서 왜 2 * i + 1 이 아닌 2 * i + 2가 되냐면, 무료로 받는 과일은 2 * i + 1 까지 이지만, 그렇게 되면 하나 뒤의 과일은 무조건 사야하는 상황이 된다. 하지만 3번 예시에서 알 수 있듯이, 무료로 받을 수 있는 과일을 삼으로써 값을 더 아낄 수 있는 경우가 있기 때문에, 결국 2 * i + 2 까지의 과일들 중 하나만 사면 되고, 그 최소값을 구해야하는 것이다.)

생각해 볼 점

1. 점화식 도출이 어려워서 다른 사람들의 접근 방식을 참고했다. 역시나 DP는 아직까지도 점화식 도출이 어려운 것 같다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL