[렛코드 문제풀이]: 캔디.

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?
 
제목은 N명의 아이들이 한 줄로 줄을 서서 모든 아이에게 rating값을 분배한다는 뜻이다.다음과 같은 규칙에 따라 아이들에게 사탕을 분배한다.
(1) 모든 아이는 적어도 사탕 하나를 나눠야 한다.
(2) 인접한 아이들 사이에는 높은 등급을 가진 아이들이 사탕을 하나 더 받는다.
 
제목의 뜻에 따라 우리는 서열을 하나 정했다.
(1) 증가 시퀀스
　　1 5 7 9
분배되기 쉬운 사탕 수는 1, 2, 3, 4
(2) 체감 시퀀스
　　8 6 4 2
분배되기 쉬운 사탕 수는 4, 3, 2, 1
(3) 단파형 시퀀스
　　1 3 5 7 6 4 
두 개의 하위 시퀀스가 있습니다. 1, 3, 5, 7 및 7, 6, 4
대응 분배 사탕 서열: 1,2,3,4 및 3,2,1
이 과정에서 7, 두 서열에서 모두 나타났지만 왼쪽에는 4개의 설탕을 분배해야 하고 오른쪽에는 3개의 설탕을 분배해야 한다. 그러면 최종 서열에서 많은 한쪽을 분배해야 한다.따라서 마지막 할당 순서는 다음과 같습니다.
　　1,2,3,4,2,1   sum= 1+2+3+4+2+1 = 13
　　7 5 4 3 9 10
두 개의 하위 시퀀스가 있습니다. 7, 5, 4, 3 및 3, 9, 10
분배는 서열에 따라 설탕을 낸다: 4, 3, 2, 1 및 1, 2, 3
기본 최소값 분배 최소당 1개.따라서 마지막 할당 순서는 다음과 같습니다.
　　4,3,2,1,2,3  sum = 4+3+2+1+2+3 = 15
(4) 다파형
　　1 2 3 9 8 7 5 2 4 6 5 3 4
무질서해 보이지만 여러 개의 증가와 감소 서열로 나눌 수 있다
점증 시퀀스: 1 2 3 9 _ _2 4 6 _ 3 4
체감 시퀀스:__ 9 8 7 5 2 _ 6 5 3 _
증분 시퀀스 할당: 1 2 3 4 _ _1 2 3 _ 1 2
마이너스 시퀀스 할당:__5 4 3 2 1 _ 3 2 1 _
최종 할당 결과: 1 2 3 5 4 3 2 1 2 3 2 1 2
 
상술한 분석을 통해 알 수 있듯이 사탕의 분배는 두 가지 서열로 나누어 분배할 수 있는데, 하나는 시비증가 서열이고, 다른 하나는 비감소 서열이다
각각 두 개의 서열up과down을 정의하고, 각각 비감소 서열과 비증가 서열을 기록한다.
(1) 처음부터 끝까지 한 번 훑어보고 증가 시퀀스 찾기 up
　　array up initial with all element equals to 1
　　for i from ratings.begin to ratings.end
　　do
　　　　if   ratings[i] > ratings [i-1] then
　　　　　　up[i] <- up[i-1] +1
　　　　end if
(2) 끝에서 끝까지 한 번 훑어보고 체감 서열down 찾기
　　array down initial with all element equals to 1
　　for i from ratings.rbegin to ratings.rend
　　do
　　　　if   ratings[i] > ratings [i+1] then
　　　　　　up[i] <- up[i+1] +1
　　　　end if
(3) up과down의 상응하는 위치를 비교하고 비교적 큰 값을 최종 결과로 선택한다
　　sum <- 0
　　for i from ratings.begin to ratings.end
　　do
　　　　sum <-  sum + max{up[i], down[i]}
　　end for
　　return sum

 1 class Solution {

 2 public:

 3     int candy(vector<int> &ratings) {

 4         int len = ratings.size();

 5         if(len<=1) return len;

 6         int i,tot=0;

 7         vector<int> up(len,1);

 8         vector<int> down(len,1);

 9         for(i=1;i<len;i++)

10             if(ratings[i]>ratings[i-1]) up[i] = up[i-1]+1;

11         for(i=len-2;i>=0;i--)

12             if(ratings[i]>ratings[i+1]) down[i]= down[i+1]+1;

13         for(i=0;i<len;i++){

14             tot += max(up[i],down[i]);

15         }

16         return tot;       

17     }

18 };

전재 출처를 밝히십시오:.감사합니다.