Candies

출처 : 해커 랭크

난이도 : 중간

알고리즘 : Greedy

 

앨리스는 유치원 선생님입니다. 그녀는 반 아이들에게 사탕을 나눠주고 싶습니다. 모든 아이들은 일렬로 앉아 있고, 각자 수업 성적에 따라 점수를 받습니다. 앨리스는 각 아이에게 최소 사탕을 하나씩 주고 싶어 합니다. 만약 두 아이가 나란히 앉으면, 점수가 높은 아이가 사탕을 더 많이 가져야 합니다. 앨리스는 자신이 사야 하는 사탕의 총 개수를 최소화하려고 합니다.

예

arr = [4, 6, 4, 5, 6, 2]

그녀는 학생들에게 다음과 같은 최소한의 양의 사탕을 줍니다.

[1,2,1,2,3,1]

그녀는 최소한 사탕 10개 를 사야 합니다.

기능 설명

아래 편집기에서 사탕 기능을 완성하세요 .

사탕에는 다음과 같은 매개변수가 있습니다.

• int n: 학급의 어린이 수
• int arr[n]: 각 학생의 평가

보고

• int: 앨리스가 사야 할 최소 사탕 수

입력 형식

첫 번째 줄에는 정수가 포함됩니다., 크기.
다음 각각lines에는 정수가 포함되어 있습니다학생의 해당 위치 평가를 나타냄.

제약 조건

• 1 ≤ n ≤ 10^5
• 1 ≤ arr[i]  10^5

샘플 입력 0

3 
1 
2 
2

샘플 출력 0

4

설명 0

여기서 1, 2, 2는 평점입니다. 두 아이의 평점이 같을 때, 각 아이에게 주어지는 사탕의 개수는 서로 다릅니다. 따라서 최적의 분포는 1, 2, 1입니다.

샘플 입력 1

10 
2 
4 
2 
6 
1 
7 
8 
9 
2 
1

샘플 출력 1

19

설명 1

최적의 분포는 다음과 같습니다.

1212123421

샘플 입력 2

8 
2 
4 
3 
5 
2 
6 
4 
5

샘플 출력 2

12

설명 2

최적의 분포는 다음과 같습니다.

12121212

 

 

----------------------------------------------------------------------------------------------------------------------------

 

문제 해독

반 아이들에게 사탕을 나누어 줄때 수업 성적과 앉아있는 순서에 따라 사탕을 줄 때 몇개의 사탕을 준비해야 하는지 구하는 문제

모든 아이들은 사탕을 1개 이상씩 받아야하며 앞에 있는 아이보다 뒤에 있는 아이가 성적이 높을 경우 사탕을 1개 더 받습니다.

 

문제접근

 

첫번째 접근 : 좌측에서 우측으로 순서대로 사탕을 줄때 앞에 있는 아이보다 뒤에 있는 아이가 성적이 높으면 1개 증가시키고 만약 뒤에 있는 아이보다 앞에 있는 아이가 성적이 낮으면 1개의 사탕을 준다.

 - 오답 발생 : 정방향만 계산하여 앞에 있는 아이와 현재 사탕을 줄 아이의 계산 결과가 올바르지 않음. 역 연산도 필요

 

두번째 접근 : 정방향 연산과 역방향 연산을 수행.

정방향 : 앞에 있는 아이보다 성적이 높으면 캔디 추가

역방향 : 뒤에 있는 아이보다 성적이 높으면 캔디 추가(단 이전 정방향 연산과 비교하였을떄 큰수를 대입)

 

public static long candies(int n, List<int> arr)
    {
        long result = 0;
        long[] candies = new long[n];
        for(int i = 0; i < n; i++)
        {
            candies[i] = 1;
        }
        
        for(int i = 1; i < n; i++)
        {
            if(arr[i] > arr[i - 1])
                candies[i] = candies[i - 1] + 1;
        }
        
        for(int i = n - 2; i >= 0; i--)
        {
            if(arr[i] > arr[i + 1])
                candies[i] = Math.Max(candies[i], candies[i + 1] + 1);
        }
            
        for(int i = 0; i < n; i++)
            result += candies[i];
        
        return result;
    }