[백준] 2961번 도영이가 만든 맛있는 음식

문제

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

고민

우선,, 문제 이해가 안돼서 시작부터 난항이었다. 

 

신맛과 쓴맛으로 곱셈덧셈을 만드는 건가?라고 생각하고 입력/출력 예시를 보는데 도저히 떠오르지 않아서 GPT한테 예시좀 많이 뽑아달라고 찡찡댔다. ㅋㅋㅋ 알고보니 신맛과 쓴맛은 각각 계산 하는거더라^.^

 

심지어 예제 3번에는 아래에 어떻게 계산된건지 과정도 적혀있다.

 

1. 신맛, 쓴맛이 같이 입력된다 => tuple로 묶기

2. 신맛은 곱하기 쓴맛은 더하기로 계산한다. => 신맛은 1에다 누적 곱하기, 쓴맛은 0에다 누적 더하기

3. 입력된 맛 개수보다 많이 조합할 수 없다. => 입력된 맛 개수만큼 선택되면 탈출하기

4. n개에서 r개를 선택한다. => 조합(백트래킹)

위 조합으로 문제를 생각하고 풀었다.

 

코드

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BackTracking
{
	// 제가 보기 편하려고 class를 생성했습니다.
    // 실제로 이렇게 하지 않고 바로 tuple선언해도 됩니다.
    class Sour
    {
        private int sourSize;

        public int SourSize
        {
            get { return this.sourSize; }
        }

        public Sour(int size)
        {
            this.sourSize = size;
        }
    }

    class Bitter
    {
        private int bitterSize;

        public int BitterSize
        {
            get { return this.bitterSize; }
        }


        public Bitter(int size)
        {
            this.bitterSize = size;
        }


    }

    class 도영이가_만든_맛있는_음식
    {
        static int ingredient; // 재료 개수
        static (Sour, Bitter)[] ingredients;
        static int answer = int.MaxValue;
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' '); // 재료 개수
            ingredient = int.Parse(input[0]);

            ingredients = new (Sour, Bitter)[ingredient]; // 재료 관리하는 배열 [(신맛, 쓴맛), (신맛, 쓴맛)]
            
            for (int i = 0; i < ingredient; i++) // 순회하면서 배열에 담기
            {
                input = Console.ReadLine().Split(' ');
                int sour = int.Parse(input[0]);
                int bitter = int.Parse(input[1]);

                ingredients[i] = (new Sour(sour), new Bitter(bitter));
            }

            BT(0, 0, 1, 0); // 레벨, 선택된 개수, 곱하기, 더하기
            Console.WriteLine(answer);
        }

        static void BT(int start, int count, int totalSour, int totalBitter) // start : 시작점, count : 선택된 수
        {
            if(start == ingredient)
            {
                if(count > 0) // 하나 이상 재료가 선택되었을 때만 계산
                {
                    int minus = Math.Abs(totalSour - totalBitter);
                    answer = Math.Min(answer, minus);
                }
                return;
            }


            // 선택
            BT(start + 1, count + 1, totalSour * ingredients[start].Item1.SourSize, totalBitter + ingredients[start].Item2.BitterSize);

            // 비선택
            BT(start+1, count, totalSour, totalBitter);
        }
    }
}

확실히 재귀가 너무 어렵다. 재귀 너무 헷갈리고 구현된 재귀 코드를 손코딩 하는건 가능하지만, 내가 그걸 구현하긴 너무 어렵다. 차라리 공식이 있으면 좋을텐데 그런 것도 없고. 계속 같은걸 풀다 보니 이런 느낌~? 으로 코드를 작성하는 지경에 이르렀다. 그러다 안되면 또 손코딩 하고,, 코딩 천재가 되고싶다.