2022.02.07 [백준] C# 1로 만들기

 

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

1463번: 1로 만들기

---

풀이

다음 문제는 3가지 조건이 있다.

1. n이 3,2의 배수가 아닐때 

2. n이 3의 배수 일 때

3. n이 2의 배수 일 때

다음 조건을 생각해 보면

우선 f(n)=f(n-1)+1 라고 f(n)을 정해놓고

if(n%3==0) f(n)=Math.Min(f(n),f(n/3)+1)

if(n%2==0) f(n)=Math.Min(f(n),f(n/2)+1)

위 처럼 if문으로 각 조건에서 이전에 설정했던 f(n)과 3또는 2으로 나눴을 때의 값을 비교하면서 최소값을 선택하여 문제를 해결했다. 

using System;
using System.Text;
using System.IO;
 
class Program
{
    static int[] count;
 
 
    static void make1(int a)
    {
        for(int i = 2; i <= a; i++)
        {
            count[i] = count[i - 1] + 1;
            if (i % 3 == 0)
            {
                count[i] = Math.Min(count[i], count[i / 3] + 1);
            }
            if (i % 2 == 0)
            {
                count[i] = Math.Min(count[i], count[i / 2] + 1);
            }
        }
        
    }
 
 
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        int n = int.Parse(sr.ReadLine());
        count = new int[n+1];
        count[0] = count[1] = 0;
        make1(n);
        sw.WriteLine(count[n]);
        sr.Close();
        sw.Close();
    }
}