[백준] 2309번 일곱 난쟁이

문제

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

코드

using System;
using System.Text;
using System.Collections.Generic;

namespace dongsik
{
    class Algorithm
    {
        static void Main(string[] str)
        {
            int[] arr = new int[9];
            int total = 0;
            for(int i = 0; i < 9; i++)            
            {
                arr[i] = int.Parse(Console.ReadLine());
                total += arr[i];
            }
            
            for(int i = 0; i <= 7; i++)
            {
                for(int j = i + 1; j <= 8; j++)
                {
                    if((total - arr[i] - arr[j]) == 100)
                    {
                        arr[i] = 0;
                        arr[j] = 0;
                        Array.Sort(arr);
                        for(int k = 2; k <= 8; k++)
                        {
                            Console.WriteLine(arr[k].ToString());
                        }
                        return;
                    }
                }
            }
            
            
        }
    }
}

고민

처음에 어떻게 풀었냐면.. 재귀로 열심히 풀어보려고 했다.. 그래서 코드를 짰는데 작렬히 전사했고 다들 어떻게 풀었는지 찾아봤더니.. 저렇게 간단한 로직이 만들어졌다.

 

우선 10개를 다 더한 뒤 2개를 빼면서 100과 일치하는 난쟁이를 찾는 것이다.

 

내가 찾던 재귀는 7명의 난쟁이를 매 계산마다 하나하나 추가하고 삭제해주기 때문에 시간도 많이 걸리고 결정적으로 틀렸다.

using System;
using System.Text;
using System.Collections.Generic;

namespace dongsik
{
    class Algorithm
    {
        static int[] arr = new int[9];
        static int cnt = 0;
        static bool[] visited = new bool[9];
        static int sum = 0;
        static StringBuilder sb = new StringBuilder();
        static bool isFind = false;
        static void Main(string[] str)
        {

            for (int i = 0; i < 9; i++)
            {
                arr[i] = int.Parse(Console.ReadLine());
            }

            Array.Sort(arr);

            Function(0, 0);
        }

        static void Function(int index, int cnt)
        {
            if (isFind == true)
            {
                return;
            }
            if (cnt >= 7 && sum == 100)
            {
                isFind = true;
                for(int j = 0; j < arr.Length; j++)
                {
                    sb.AppendLine(arr[j].ToString());
                }
                return;
            }
            {
                for (int i = 0; i < 9; i++)
                {
                    if (!visited[i])
                    {
                        visited[i] = true; // 방문처리
                        sum += arr[i]; // 더하기
                        Function(index + 1, cnt + 1);
                        visited[i] = false;
                        sum -= arr[i];
                    }
                }
            }
        }
    }
}

이게 내가 적던 코드다.. 진짜.. 너무 헷갈린다 재귀 ㅠ 설명 들으면 처음엔 이해가 되는 거 같다가도 또 하다보면 이해가 안되서 눈물만 광광 나온다.