C# 프로그래머스 Level2

**참고사이트 : https://jaehee1007.tistory.com/85

1. 먼저 info의 정보를 apeech로 저장하고, lion의 데이터를 저장한다
2. 백트랙킹을 사용해 DFS를 구현했다.
3. 백트래킹을 사용한 이유는 전체 노드를 다 확인하며 돌아왔다 다른값을 넣어보는 조건이 있다.(제일 작은 최고점수 + 최고점이 동일할경우 작은 점수의 합)

using System;
using System.Collections.Generic;

public class Solution {
    
    public int[] arr = new int[11];
    
    public int[] solution(int n, int[] info)
    {
        int max = 0;

        Dictionary<int, int> lionDic = new Dictionary<int, int>();
        Dictionary<int, int> apeechDic = new Dictionary<int, int>();

        for (int i = 0; i < info.Length; i++)
        {
            apeechDic.Add(10 - i, info[i]);
            lionDic.Add(10 - i, 0);
        }

        DFS(n, 10,lionDic, apeechDic,ref max);

        int[] answer = max <= 0 ? new int[] { -1 } : (int[])arr.Clone();
        
        return answer;
    }

    public void DFS(int n, int curIndex, Dictionary<int, int> lionDic, Dictionary<int, int> apeechDic, ref int max)
    {
        if (n == 0)
        {
            Winer(lionDic, apeechDic, ref max);
            return;
        }

        if (curIndex < 0)
        {
            lionDic[0] = n;
            Winer(lionDic, apeechDic, ref max);
            lionDic[0] = 0;
            return;
        }

        if (apeechDic[curIndex] < n)
        {
            lionDic[curIndex] = apeechDic[curIndex] + 1;
            DFS(n - (apeechDic[curIndex] + 1), curIndex - 1, lionDic, apeechDic,ref max);
            lionDic[curIndex] = 0;
        }


        DFS(n, curIndex - 1, lionDic, apeechDic, ref max);
    }

    public void Winer(Dictionary<int,int> lionDic, Dictionary<int,int> apeechDic,ref int max)
    {
        List<int> sumList = new List<int>();
        int[] lionArr = new int[11];
        int sum = 0;

        for (int i = 0; i < apeechDic.Count; i++)
        {
            if (lionDic[i] == 0 && apeechDic[i] == 0)
            {
                lionArr[i] = 0;
                sumList.Add(0);
            }
            else if (lionDic[i] <= apeechDic[i])
            {
                lionArr[i] = lionDic[i];
                sumList.Add(-i);
            }
            else
            {
                lionArr[i] = lionDic[i];
                sumList.Add(i);
            }
        }

        var sample = (int[])lionArr.Clone();

        for(int i = 0; i < lionArr.Length; i++)
        {
            lionArr[i] = sample[10 - i];
        }


        for(int i = 0; i < sumList.Count; i++)
        {
            sum += sumList[i];
        }

        if(sum > max)
        {
            max = sum;
            arr = (int[])lionArr.Clone();
        }
        else if(sum == max)
        {
            for(int i = lionArr.Length - 1; i >= 0; i--)
            {
                if (arr[i] < lionArr[i])
                {
                    arr = (int[])lionArr.Clone();
                    break;
                }
                else if(arr[i] > lionArr[i])
                    break;
            }
        }
    }
}