[C#] 백준 16953번 문제풀이

문제번호: 16953

문제명: A → B

문제링크: https://www.acmicpc.net/problem/16953

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다.

 

안녕하세요. 오늘은 두가지 연산 규칙을 통해 A를 B로 만들 수 있는 최소 연산수를 구하는 문제를 풀어보았습니다. 저는 재귀함수를 통해 모든 경우의 수를 탐색하였습니다.

다음은 정답코드입니다.

 

public static void Main()
{
    Console.OutputEncoding = Encoding.UTF8;
    using var sr = new StreamReader(Console.OpenStandardInput());
    using var sw = new StreamWriter(Console.OpenStandardOutput());

    int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    int A = input[0];
    int B = input[1];

    List<int> list = new List<int>();

    Recallmethod(A, 1);
    void Recallmethod(BigInteger num, int count)
    {
        if (num == B)
            list.Add(count);
        else if (num > B) return;

        string sNum = num.ToString() + 1;
        BigInteger sNumToInt = BigInteger.Parse(sNum);
        Recallmethod(sNumToInt, count + 1);

        Recallmethod(num * 2, count + 1);
    }

    if (list.Count > 0)
        sw.WriteLine(list.Max());
    else
        sw.WriteLine(-1);

    sr.Close();
    sw.Close();
}