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

NaZZU 2024. 4. 15. 00:33

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace 연습장
{
    internal class _1463_boj
    {
        public void boj_1463()
        {
            int X = int.Parse(Console.ReadLine());
 
            int[] dp = new int[X + 1];
 
            dp[1] = 0;
 
            for (int i = 2; i < dp.Length; i++)
            {
                if (i % 6 == 0)
                    dp[i] = Math.Min(1 + dp[i / 3], 1 + dp[i / 2]);
                else if (i % 3 == 0)
                    dp[i] = Math.Min(1 + dp[i / 3], 1 + dp[i - 1]);
                else if (i % 2 == 0)
                    dp[i] = Math.Min(1 + dp[i / 2], 1 + dp[i - 1]);
                else
                    dp[i] = 1 + dp[i - 1];
 
            }
 
            Console.WriteLine(dp[X]);
        }
    }
}
 
Colored by Color Scripter

cs

6의 배수에 대한 처리를 하지 않으면 문제가 생기므로 6의 배수일 경우 2로 나눈 경우와 3으로 나눈 경우를 비교해서 더 작은 것을 넣어줘야 한다.