백준 1463번 1로 만들기 문제(C#)

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

개요

정수 N을 1로 만들기 위해 다음 세 가지 연산 중 하나를 최소 횟수로 사용하려고 한다.

• 3으로 나누어 떨어지면 3으로 나누기

• 2로 나누어 떨어지면 2로 나누기

• 1 빼기

최소 연산 횟수를 구하는 문제이다.

문제 이해 및 접근

• 입력값이 주어지면 1이 될 때까지 연산을 수행한다.

• 각 숫자 i에 대해 최소 연산 횟수 dp[i]를 저장한다.

• dp[i]를 구하려면, i-1, i/2, i/3(나누어 떨어질 경우) 중 최소값에 1을 더하면 된다.

풀이

1부터 N까지 순차적으로 dp 배열을 채워나간다.

점화식:

dp[i] = dp[i - 1] + 1  
if i % 2 == 0, dp[i] = min(dp[i], dp[i / 2] + 1)  
if i % 3 == 0, dp[i] = min(dp[i], dp[i / 3] + 1)

• 이 과정을 거치면 dp[N]이 최소 연산 횟수가 된다.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace backjoon
{
    internal class Program
    {

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

            dp[1] = 0;

            for (int i = 2; i <= n; i++)
            {
                dp[i] = dp[i - 1] + 1;

                if (i % 2 == 0)
                    dp[i] = Math.Min(dp[i], dp[i / 2] + 1);

                if (i % 3 == 0)
                    dp[i] = Math.Min(dp[i], dp[i / 3] + 1);
            }

            Console.WriteLine(dp[n]);
        }
    }
}

느낀 점

• DP의 기본적인 활용 사례라 공부하기 좋았다.

• 바텀업 방식이 중복 계산을 없애고 효율적임을 확인했다.

• 재귀(탑다운) 방식도 가능하지만, 오버헤드가 크고 스택 깊이 문제도 있어 바텀업이 더 안전하다.