백준 C# - 1463 +) 풀이

DP를 이용해서 풀어야한다.

DP알아보러 가기

C# - 다이나믹 프로그래밍(DP)

---

풀이

DP의 점화식을 구해보자

dp[i] = dp[i - 1] + 1   // 1을 빼는 경우
dp[i] = min(dp[i], dp[i / 2] + 1)   // 2로 나누는 경우
dp[i] = min(dp[i], dp[i / 3] + 1)   // 3으로 나누는 경우

왜 점화식 끝에 1을 더해요?

 dp[i]는 i를 1로 만들기 위해 필요한 최소 연산 횟수를 나타내므로 각각의 연산이 수행될때마다 count하는 것이다.

---

1. 보텀업 방식

dp[2]에서부터 dp[n]까지 차례로 계산한다.

for (int i = 2; i <= n; i++)
{
    dp[i] = dp[i - 1] + 1; // 1을 빼는 경우
    if (i % 3 == 0) dp[i] = Math.Min(dp[i], dp[i / 3] + 1); // 3으로 나누는 경우
    if (i % 2 == 0) dp[i] = Math.Min(dp[i], dp[i / 2] + 1); // 2로 나누는 경우.
}

만약 n이 5인경우

---

2. 탑다운 방식

이미 계산된 경우 반환

static int TopDown(int n, int[] dp) 
{
    if (n == 1) return 0; // 1인경우 0반환

    if (dp[n] > 0) return dp[n]; // 이미 계산한 값이 있다면 반환

    dp[n] = TopDown(n - 1, dp) + 1; // 1을 빼는 경우
    if (n % 2 == 0) dp[n] = Math.Min(dp[n], TopDown(n / 2, dp) + 1); // 2로 나누는 경우
    if (n % 3 == 0) dp[n] = Math.Min(dp[n], TopDown(n / 3, dp) + 1); // 3으로 나누는 경우

    return dp[n];
}

만약 n이 5인경우

---

보텀업 방식 코드 전문

using System;
using System.Collections.Generic;
using System.Linq;

namespace baek2
{
   
    class Program
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            int[] dp = new int[n + 1];


            for (int i = 2; i <= n; i++)
            {
                dp[i] = dp[i - 1] + 1; // 1을 빼는 경우
                if (i % 3 == 0)
                {
                    dp[i] = Math.Min(dp[i], dp[i / 3] + 1); // 3으로 나누는 경우
                }
                if (i % 2 == 0)
                {
                    dp[i] = Math.Min(dp[i], dp[i / 2] + 1); // 2로 나누는 경우.
                }
            }
            Console.WriteLine(dp[n]);
        }
    }
}

---

탑다운 방식 코드 전문

using System;
using System.Collections.Generic;
using System.Linq;

namespace baek2
{
    class Program
    {
        static int TopDown(int n, int[] dp)
        {
            if (n == 1) return 0; 

            if (dp[n] > 0) return dp[n]; 

            dp[n] = TopDown(n - 1, dp) + 1; // 1을 빼는 경우
            if (n % 2 == 0) dp[n] = Math.Min(dp[n], TopDown(n / 2, dp) + 1); // 2로 나누는 경우
            if (n % 3 == 0) dp[n] = Math.Min(dp[n], TopDown(n / 3, dp) + 1); // 3으로 나누는 경우

            return dp[n];
        }
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            int[] dp = new int[n + 1];
            Console.Write(TopDown(n, dp));
        }

    }
}