MinimumStepstoOneTopdownApproach는 하향식(Top-down) 동적 계획법 기법으로, 정수 n과 정수 배열(dp 배열)을 입력으로 받습니다. 이 문제는 주어진 수 n을 다음 세 가지 연산만 사용하여 1로 만들 때 필요한 최소 연산 횟수를 구하는 것입니다.
- n이 3으로 나누어떨어지면 3으로 나눕니다.
- n이 2로 나누어떨어지면 2로 나눕니다.
- 언제든 가능한 연산으로, n에서 1을 뺍니다.
예를 들어 n이 10이라면 10 → 9 → 3 → 1 순서로 진행되며, 총 3단계가 필요합니다.
알고리즘 동작 과정
- 초기 조건 검사: n이 1인지 확인합니다. n이 1이면 더 이상 연산이 필요 없으므로 0을 반환합니다.
- 변수 초기화: op1, op2, op3 세 변수를 각각 최댓값(int.MaxValue)으로 초기화합니다.
- 재귀 호출: n mod 3이 0이면 n/3에 대해 재귀 호출한 결과를 op1에 저장하고, n mod 2가 0이면 n/2에 대해 재귀 호출한 결과를 op2에 저장합니다. 마지막으로 항상 n에서 1을 뺀 값으로 재귀 호출하여 그 결과를 op3에 저장합니다.
- 최솟값 계산 및 저장: Math.Min 메서드를 사용해 세 연산 결과 중 최솟값을 구하고, 여기에 1을 더한 값을 dp 배열에 저장한 뒤 반환합니다. dp 배열에 결과를 저장함으로써(메모이제이션) 동일한 하위 문제의 중복 계산을 방지할 수 있습니다.
예제 코드
public class DynamicProgramming{
public int MinimumStepstoOneTopdownApproach(int n, int[] dp){
if (n == 1){
return 0;
}
int op1, op2, op3;
op1 = int.MaxValue; op2 = int.MaxValue; op3 = int.MaxValue;
if (n % 3 == 0){
op1 = MinimumStepstoOneTopdownApproach(n / 3, dp);
}
if (n % 2 == 0){
op2 = MinimumStepstoOneTopdownApproach(n / 2, dp);
}
op3 = MinimumStepstoOneTopdownApproach(n - 1, dp);
int ans = Math.Min(Math.Min(op1, op2), op3) + 1;
return dp[n] = ans;
}
}
static void Main(string[] args){
DynamicProgramming dp = new DynamicProgramming();
int[] dpArr = new int[150];
Console.WriteLine(dp.MinimumStepstoOneTopdownApproach(10, dpArr));
}
실행 결과
3
n이 10일 때 위 프로그램은 3을 출력합니다. 즉, 10을 1로 만드는 데 최소 3번의 연산이 필요하다는 의미입니다.
복잡도 분석
시간 복잡도 — O(N): 메모이제이션 덕분에 각 수는 한 번만 계산됩니다.
공간 복잡도 — O(N): 재귀 호출 스택과 dp 배열에 N 크기의 공간이 사용됩니다.