C++의 사탕

N명의 어린이가 있다고 가정하고 그들은 일렬로 서 있습니다. 여기에서 각 어린이에게 등급 값이 할당됩니다. 우리는 다음 요구 사항에 따라 이러한 어린이에게 사탕을 공급하고 있습니다 -

각 어린이는 적어도 하나의 사탕을 가지고 있어야 합니다.
평점이 높은 아이들은 이웃보다 더 많은 사탕을 받습니다.

우리가 주어야 하는 사탕의 최소 수를 찾아야 합니까?

따라서 입력이 [1,1,3]과 같으면 출력은 4가 됩니다. 따라서 각각 1, 1, 2개의 사탕을 얻습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=배열 등급의 크기, 크기가 n인 dp라는 배열을 만들고 1
을 사용하여 채웁니다.
ret :=0
범위 1에서 n – 1까지의 i에 대해
- 등급[i]> 등급[i – 1]이면 dp[i] :=dp[i - 1] + 1
범위 n - 2에서 0까지의 i에 대해
- Ratings[i]> Ratings[i + 1]이면 dp[i] :=dp[i] 및 dp[i + 1] + 1의 최대값
ret :=dp의 요소들의 합
리턴 렛

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int candy(vector<int>& ratings) {
      int n = ratings.size();
      vector <int> dp(n, 1);
      int ret = 0;
      for(int i = 1; i < n; i++){
         if(ratings[i] > ratings[i - 1]){
            dp[i] = dp[i - 1] + 1;
         }
      }
      for(int i = n - 2; i >= 0; i--){
         if(ratings[i] > ratings[i + 1]){
            dp[i] = max(dp[i], dp[i + 1] + 1);
         }
      }
      for(int i = 0; i < n; i+=1){
         ret += dp[i];
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,3};
   cout << (ob.candy(v));
}

입력

[1,1,3]