C#에서 동적 계획법(Dynamic Programming)의 상향식(Bottom-up) 접근 방식을 활용하면 '1까지의 최소 단계(Minimum Steps to One)' 문제를 효율적으로 해결할 수 있습니다. 이 문제는 주어진 정수 n을 1로 만들기 위해 필요한 최소 연산 횟수를 구하는 것으로, 사용할 수 있는 연산은 다음 세 가지입니다.
- n에서 1을 뺀다
- n이 2로 나누어떨어질 경우 2로 나눈다
- n이 3으로 나누어떨어질 경우 3으로 나눈다
상향식(Bottom-up) 접근 방식의 동작 원리
상향식 접근 방식은 재귀 호출 없이 반복문을 사용하여 가장 작은 값부터 차례대로 dp 배열을 채워 나가는 기법입니다. 알고리즘의 진행 과정은 다음과 같습니다.
- 정수 n을 입력받습니다. 매개변수 n은 목표 숫자를 나타냅니다.
- 초기 조건에서 n이 1인지 검사하고, n이 1이면 연산이 필요 없으므로 0을 반환합니다.
- 세 가지 연산의 결과를 저장할 op1, op2, op3을 최대값(int.MaxValue)으로 초기화합니다.
- 현재 값이 3으로 나누어떨어지면 dp[i/3]의 값을 op1에 저장합니다.
- 현재 값이 2로 나누어떨어지면 dp[i/2]의 값을 op2에 저장합니다.
- 항상 가능한 연산인 1을 빼는 경우의 값 dp[i-1]을 op3에 저장합니다.
- 세 연산 중 최솟값에 1(연산 횟수)을 더하여 dp[i]에 저장합니다.
- 모든 반복이 끝나면 dp 배열에 저장된 최종 값을 반환합니다.
시간 복잡도: O(N)
공간 복잡도: O(N)
예제 코드
using System;
public class DynamicProgramming {
public int MinimumStepsToOneBottomUpApproach(int n) {
int[] dp = new int[n + 1];
dp[1] = 0;
for (int i = 2; i <= n; i++) {
int op1 = int.MaxValue, op2 = int.MaxValue, op3 = int.MaxValue;
if (i % 3 == 0) {
op1 = dp[i / 3];
}
if (i % 2 == 0) {
op2 = dp[i / 2];
}
op3 = dp[i - 1];
dp[i] = Math.Min(Math.Min(op1, op2), op3) + 1;
}
return dp[n];
}
}
class Program {
static void Main(string[] args) {
DynamicProgramming dp = new DynamicProgramming();
Console.WriteLine(dp.MinimumStepsToOneBottomUpApproach(10));
}
}실행 결과
3결과 분석
입력값이 10일 때 출력이 3인 이유는 다음 경로를 따르기 때문입니다.
10 → 9 → 3 → 1
- 10에서 1을 뺌 (10 → 9)
- 9를 3으로 나눔 (9 → 3)
- 3을 3으로 나눔 (3 → 1)
이처럼 상향식 접근 방식은 dp 배열을 작은 값부터 순차적으로 계산하므로, 재귀 기반의 하향식(Top-down) 방식과 달리 함수 호출 오버헤드가 없어 실행 속도 면에서 유리한 경우가 많습니다.