백준# 2961 - 도영이가 만든 맛있는 음식

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

2961번: 도영이가 만든 맛있는 음식

재귀호출로 분류된 2961 - 도영이가 만든 맛있는 음식 입니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
 
namespace _2961
{
    class Program
    {
        public class Cook
        {
            public static List<Cook> cooks;
            public static int totalCount;
            public static int minDiff;
 
            public int count;
            public int sour;
            public int bitter;
 
            public Cook(int sour, int bitter, int count = 0)
            {
                this.count = count;
                this.sour = sour;
                this.bitter = bitter;
            }
 
            public static Cook operator +(Cook c1, Cook c2)
            {
                return new Cook(c1.sour * c2.sour, c1.bitter + c2.bitter, c1.count + 1);
            }
 
            public static void Recur(Cook c, int index)
            {
                if(index == totalCount)
                {
                    if(c.count != 0)
                    {
                        int diff = Math.Abs(c.sour - c.bitter);
                        minDiff = minDiff > diff ? diff : minDiff;
                    }
                    return;
                }
 
                else
                {
                    Recur(c, index + 1);
                    c.count++;
                    Recur(c + cooks[index], index + 1);
                }
 
            }
        }
      
        static void Main(string[] args)
        {
            Cook.cooks = new List<Cook>();
            Cook.totalCount = int.Parse(Console.ReadLine());
            Cook.minDiff = int.MaxValue;
 
            for(int i = 0; i < Cook.totalCount; i++)
            {
                int[] input = Console.ReadLine()
                    .Split(' ').Select(x => int.Parse(x)).ToArray();
                Cook.cooks.Add(new Cook(input[0], input[1]));
            }
 
            Cook.Recur(new Cook(1, 0), 0);
 
            Console.WriteLine(Cook.minDiff);
        }
    }
}
 

Cook이라는 클래스를 하나 정의했습니다.

 

신맛, 쓴맛이 있고 요리를 하나도 섞지 않을 경우를 대비해 카운트를 하나 넣었습니다.

계산을 편하게 하려고 연산자 오버로딩을 사용했습니다.

Cook c1 + Cook c2 를 더할 경우 둘의 신맛은 곱하고 쓴맛은 더하도록 했습니다.

 

해결 방법 입니다.

ex)

4

1 7

2 6

3 8

4 9

 

처음 1 7의 요리를 만난다면 도영이가 할 수 있는건 두가지로 나뉩니다. 이 요리를 섞거나 안섞거나.

섞은 상태에서 진행할 수 있고 섞지 않고 진행할 수 있습니다.

 

다음 2 6의 요리를 만나면 마찬가지로 이 요리를 섞거나 섞지 않거나 둘로 나뉩니다.

두번째 요리까지 진행하면 4가지의 결과가 나올 수 있습니다.

1 : 선택, 2 : 선택 / 1 : x, 2 : 선택 / 1 : x, 2 : x / 1 : 선택, 2 : x

 

3번째 3 8 또한 마찬가지 입니다. 요리를 섞거나 안섞을 수 있습니다.

이 2번 요리에서 나올 경우의 수 * 2가지의 경우가 나옵니다.

 

 

이것을 일반화 시키면 현재 요리를 섞거나 섞지 않은 상태 그대로 그 뒤를 쭉 진행시켜 봐야 한다는 것입니다.

그것을 재귀로 호출해주고 각 재귀호출 된 메서드는 만난 요리를 섞거나 섞지 않음을 분기하고

반복하며 마지막 까지 진행합니다.

 

재귀된 메서드가 끝에 도달했다면 자신이 섞은 요리의 맛이 담겨있을 것이고 아무것도 안섞인게 아니라면

그 맛을 최소 맛차이와 비교해 업데이트 하면 되겠습니다.

 

최초 재귀 호출시 맛을 1, 0으로 세팅하고 진행했습니다.