[C#]백준 1463번: 1로 만들기

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

1463번: 1로 만들기

---

• 문제

---

• 문제풀이

다이나믹 프로그래밍을 사용하였다. 재귀 방식을 사용하여 문제를 풀었다.

 

---

• 코드 1

using System;

class MainClass
{
    public static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());

        int[] dp = new int[n + 1];
        int count = FindMinOperations(n, dp);

        Console.WriteLine(count);
    }

    public static int FindMinOperations(int n, int[] dp)
    {
        if (n == 1)
        {
            return 0;
        }

        if (dp[n] > 0) // 이미 계산한 값이 있다면 그 값을 사용
        {
            return dp[n];
        }

        int minOperations = FindMinOperations(n - 1, dp) + 1; // n에서 1을 빼는 경우
        if (n % 2 == 0)
        {
            minOperations = Math.Min(minOperations, FindMinOperations(n / 2, dp) + 1); // n을 2로 나누는 경우
        }
        if (n % 3 == 0)
        {
            minOperations = Math.Min(minOperations, FindMinOperations(n / 3, dp) + 1); // n을 3으로 나누는 경우
        }

        dp[n] = minOperations; // 최소 연산 횟수를 저장
        return minOperations;
    }
}

 

---

• 후기

다이나믹 프로그래밍은 항상 접근하기 어렵다. 많이 노력해야겠다.