[ BOJ/C# ] 1463 1로 만들기

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

1463번: 1로 만들기

다이나믹 프로그래밍 유형으로 초반에 노가다를 하여 규칙을 찾아내 앞의 값을 이용하여 푸는 문제이다. 

중복 조건일때, 최솟값에 1을 더해주도록 찾아나갔다. 

using System;
using System.Text;

namespace B1463
{
    class Program
    {
        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(sr.ReadLine());
            int[] dp = new int[1000001];
            dp[2] = 1;
            dp[3] = 1;
            if (n >= 4)
            {
                for (int i = 4; i <= n; i++)
                {
                    if (i % 3 == 0 && i % 2 == 0)
                    {
                        dp[i] = (dp[i / 3] > dp[i / 2] ? dp[i / 2] : dp[i / 3]) + 1;
                        //if () dp[i] = dp[i / 2] + 1;
                        //else dp[i]= dp[i / 3] + 1;
                    }
                    else if (i % 3 == 0)
                    {
                        dp[i] = (dp[i - 1] > dp[i / 3] ? dp[i / 3] : dp[i - 1]) + 1;
                        //if (dp[i - 1] > dp[i / 3]) dp[i] = dp[i / 3] + 1;
                        //else dp[i] = dp[i - 1] + 1;
                    }
                    else if (i % 2 == 0)
                    {
                        dp[i] = (dp[i - 1] > dp[i / 2] ? dp[i / 2] : dp[i - 1]) + 1;
                        //if (dp[i - 1] > dp[i / 2]) dp[i] = dp[i / 2] + 1;
                        //else dp[i] = dp[i - 1] + 1;
                    }
                    else dp[i] = dp[i - 1] + 1;
                }
            }
            sw.Write(dp[n]);
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}

제출 코드

using System;
using System.Text;

namespace B1463
{
    class Program
    {
        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(sr.ReadLine());
            int[] dp = new int[1000001];
            dp[2] = 1;
            dp[3] = 1;
            if (n >= 4)
            {
                for (int i = 4; i <= n; i++)
                {
                    if (i % 3 == 0 && i % 2 == 0) dp[i] = (dp[i / 3] > dp[i / 2] ? dp[i / 2] : dp[i / 3]) + 1;
                    else if (i % 3 == 0) dp[i] = (dp[i - 1] > dp[i / 3] ? dp[i / 3] : dp[i - 1]) + 1;
                    else if (i % 2 == 0) dp[i] = (dp[i - 1] > dp[i / 2] ? dp[i / 2] : dp[i - 1]) + 1;
                    else dp[i] = dp[i - 1] + 1;
                }
            }
            sw.Write(dp[n]);
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}