[알고리즘] DP구현: 정수 N을 1로 만드는 최소 연산 횟수 (Top-Down vs Bottom-Up)

 

앞 글에서 동적 프로그래밍에 대해 알아보았었다.

 

이번 글에서는 동적 프로그래밍을 활용해서

정수 N을 1로 만드는 최소 연산 횟수 문제를 간단하게 구현해보도록 하자! 

 

 

0. 문제 정의

정수 N이 주어졌을 때, 다음 세 연산만을 사용하여 N을 1로 만드는 최소 연산 횟수를 구하는 문제를 해결해보자. 

• N이 3으로 나누어 떨어지면 → N = N / 3
• N이 2로 나누어 떨어지면 → N = N / 2
• 항상 가능 → N = N - 1

목표는 연산 횟수를 최소화하는 것 !! 

핵심 포인트: 여러 선택지 중에서 최소 횟수를 선택해야 하는 최적화 문제

 

 

 

이 문제는 중복되는 계산이 많기 때문에 동적 계획법(DP)이 적합한 문제다.

 

 

DP를 적용하면 작은 문제부터 큰 문제까지 최적해를 점차 만들어 나갈 수 있다.

 

DP 방식은 두 가지로 구현할 수 있다:

1. Top-Down (재귀 + 메모이제이션)
   • 큰 문제를 작은 문제로 나누어 재귀적으로 해결
   • 이미 계산한 값은 dp[] 배열에 저장해서 중복 계산 방지
2. Bottom-Up (반복문)
   • 작은 값부터 차례대로 최적값을 계산
   • 재귀 없이 안정적, 빠른 계산 가능

2가지 방법으로 각각 구현해보도록 하자! 

 

 

 

1. Top-Down 방식 구현 

앞 글에서 보았던 점화식은 다음과 같다. 

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

dp[n] : n을 1로 만드는 최소 연산 횟수

 

 

점화식을 머릿속에 새기면서 이제 구현 내용을 살펴보도록 하자. 

 

 

전역 변수

vector<int> dp;     // dp[n] = n을 1로 만드는 최소 연산 횟수
vector<int> Prev;   // Prev[n] = n 이전 값 (경로 추적)

• dp 배열 
  • n을 1로 만드는 최소 연산 횟수
  • Top-Down 에서는 이미 계산한 값 저장 (메모이제이션) 용도
• Prev 배열
  • n에서 최소 연산으로 이동한 다음 숫자
  • 나중에 연산 경로 출력할 때 사용 

 

slove(n) 함수 - 핵심

slove(n) 함수 -> 정수 n을 1로 만드는 최소 연산 횟수를 반환한다

 

1. 종료 조건

if (n == 1) return 0;

• 1은 이미 목표 상태 →  연산을 더 할 필요가 없음 → 0회

 

2. 메모이제이션 체크

if (dp[n] != -1) return dp[n];

• 이미 최소 연산 횟수를 계산한 적 있는 경우 → 다시 계산하지 않고 바로 반환 → 중복 계산 제거 (DP 핵심)

 

 

3. (3가지 경우의 연산) 1 연산

dp[n] = solve(n - 1) + 1;
Prev[n] = n - 1;

• n → n-1
  • 연산 1번 수행
• (n-1) → 1
  • solve(n - 1) 번의 연산 필요

그래서 

n → 1 총 연산 횟수 = solve(n - 1) + 1

일단 이 값을 기본값으로 설정하고, Prev에도 “n 다음은 n-1이다”라고 기록하자. 

 

 

 

4. (3가지 경우의 연산) 2로 나누기 

if (n % 2 == 0)
{
    int temp = solve(n / 2) + 1;

    // 기존 값과 비교 
    if (temp < dp[n]) 
    {
        dp[n] = temp; 
        Prev[n] = n / 2;
    }
}

• 2로 나누어 떨어질 때만 가능하며,
• 1 연산보다, 2로 나누는 연산이 더 적은 횟수라면? →  더 좋은 선택이므로 갱신한다. 

 

 

5. (3가지 경우의 연산) 3으로 나누기 

if (n % 3 == 0)
{
    int temp = solve(n / 3) + 1;

	// 지금까지 값과 비교 
    if (temp < dp[n])
    {
        dp[n] = temp;
        Prev[n] = n / 3;
    }
}

• 3으로 나누어 떨어질 때만 가능하며,
• 지금까지의 연산보다, 3으로 나누는 연산이 더 적은 횟수라면? →  더 좋은 선택이므로 갱신한다. 

 

 

코드 예시

// Top-Down 재귀 함수
int solve(int n)
{
    // 1이면 연산 필요 없음
    if (n == 1) return 0;

    // 이미 계산된 경우 : 중복 계산을 피하기 위해 저장된 값을 바로 반환
    if (dp[n] != -1) return dp[n];

    // dp[현재값] = dp[다음값] + (현재에서 다음으로 가는 연산 1번)
    
    // 1) -1 연산
    dp[n] = solve(n - 1) + 1;
    Prev[n] = n - 1;

    // 2) 2로 나누는 경우
    if (n % 2 == 0)
    {
        int temp = solve(n / 2) + 1;
        if (temp < dp[n])
        {
            dp[n] = temp;
            Prev[n] = n / 2;
        }
    }

    // 3) 3으로 나누는 경우
    if (n % 3 == 0)
    {
        int temp = solve(n / 3) + 1;
        if (temp < dp[n])
        {
            dp[n] = temp;
            Prev[n] = n / 3;
        }
    }

    return dp[n]; // 최소 연산 횟수를 반환
}

 

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// [ 정수 N을 1로 만드는 최소 연산 횟수 : TopDown ]

vector<int> dp;     // dp[n] = n을 1로 만드는 최소 연산 횟수
vector<int> Prev;   // prev[n] = n 이전 값 (경로 추적)

// Top-Down 재귀 함수
int solve(int n)
{
    // 1이면 연산 필요 없음
    if (n == 1) return 0;

    // 이미 계산된 경우
    if (dp[n] != -1) return dp[n];


    // 1) -1 연산
    dp[n] = solve(n - 1) + 1;
    Prev[n] = n - 1;

    // 2) 2로 나누는 경우
    if (n % 2 == 0)
    {
        int temp = solve(n / 2) + 1;

        // 기존 값과 비교 
        if (temp < dp[n]) 
        {
            dp[n] = temp; 
            Prev[n] = n / 2;
        }
    }

    // 3) 3으로 나누는 경우
    if (n % 3 == 0)
    {
        int temp = solve(n / 3) + 1;

		// 지금까지 값과 비교 
        if (temp < dp[n])
        {
            dp[n] = temp;
            Prev[n] = n / 3;
        }
    }

    return dp[n];
}

int main()
{
    cout << "(1로 만들기 문제 - TopDown) 숫자를 입력하세요: ";
    int N;
    cin >> N;

    // dp 초기화 (-1 = 아직 계산 안 됨)
    dp.assign(N + 1, -1);
    Prev.assign(N + 1, 0);

    // 최소 연산 횟수 계산
    int result = solve(N);
    cout << "최소 연산 횟수: " << result << endl;

    // 경로 추적
    vector<int> path;
    int current = N;
    while (true)
    {
        path.push_back(current);
        if (current == 1) break;
        current = Prev[current];
    }

    // 경로 출력 (앞에서부터)
    cout << "연산 경로: ";
    for (int i = 0; i < path.size(); i++)
    {
        if (i > 0) cout << " -> ";
        cout << path[i];
    }
    cout << endl;

    return 0;
}

 

 

 

 

2. Bottom-Up 방식 구현 

Bottom-Up 방식은 작은 값부터 차례대로 답을 만들어서 큰 값의 답을 구하는 방식

• 작은 값부터 순서대로 dp[i] 계산
• 이미 계산된 작은 값들을 이용해서 큰 값의 최소 연산 횟수를 구한다.
• 반복문으로 구현해서 재귀 필요 없음

 

선언

vector<int> dp(N + 1, 0);
vector<int> Prev(N + 1, 0);

• dp[i] = i를 1로 만드는 최소 연산 횟수
  • Top-Down과 의미는 동일하지만, Bottom-Up에서는 미리 전부 계산해 나간다. 
• Prev[i] = i에서 최소 연산으로 이동한 다음 숫자 (경로 출력용)

 

초기값

dp[1] = 0;

• 1 은 이미 목표 상태(1)이므로, 연산 횟수는 0

Bottom-Up의 시작점

 

 

DP 계산 반복문 - 핵심

1. 2부터 시작

for (int i = 2; i <= N; i++) 
{
	...
}

앞에서 말했듯 1은 이미 목표 상태이니까 2부터 시작 

 

 

2. (3가지 경우의 연산) -1 연산

// 1) -1 연산
dp[i] = dp[i - 1] + 1;
Prev[i] = i - 1;

• i → i-1
  • 연산 1번
• (i-1) → 1
  • dp[i-1] 번

일단 이 값을 기본값으로 설정

 

 

3. (3가지 경우의 연산) 2로 나누기  

// 2) 2로 나누어 떨어지면
if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) 
{
    dp[i] = dp[i / 2] + 1;
    Prev[i] = i / 2;
}

 

 

4. (3가지 경우의 연산) 3으로 나누기 

// 3) 3으로 나누어 떨어지면
if (i % 3 == 0 && dp[i / 3] + 1 < dp[i]) 
{
    dp[i] = dp[i / 3] + 1;
    Prev[i] = i / 3;
}

 

이 시점에서 

dp[i] = i를 1로 만드는 최소 연산 횟수
Prev[i] = 그때 선택한 이전 값

 

 

 

코드 예시

vector<int> dp(N+1, 0);
vector<int> Prev(N+1, 0);
dp[1] = 0;

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

    if (i % 2 == 0 && dp[i/2] + 1 < dp[i])
    {
        dp[i] = dp[i/2] + 1;
        Prev[i] = i / 2;
    }

    if (i % 3 == 0 && dp[i/3] + 1 < dp[i])
    {
        dp[i] = dp[i/3] + 1;
        Prev[i] = i / 3;
    }
}

 

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// [ 정수 N을 1로 만드는 최소 연산 횟수 : BottomUp ]

int main() 
{
    cout << "(1로 만들기 문제 - BottomUp) 숫자를 입력하세요: ";
    int N;
    cin >> N;

    // dp[i] = i를 1로 만드는 최소 연산 횟수
    vector<int> dp(N + 1, 0);

    // 경로 추적용 => prev[i] = i를 만들기 직전의 값
    vector<int> Prev(N + 1, 0);

    dp[1] = 0; // 기본값 : 1은 이미 1이므로 연산 0회

    for (int i = 2; i <= N; i++) 
    {
        // 1) -1 연산
        dp[i] = dp[i - 1] + 1;
        Prev[i] = i - 1;

        // 2) 2로 나누어 떨어지면
        if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) 
        {
            dp[i] = dp[i / 2] + 1;
            Prev[i] = i / 2;
        }

        // 3) 3으로 나누어 떨어지면
        if (i % 3 == 0 && dp[i / 3] + 1 < dp[i]) 
        {
            dp[i] = dp[i / 3] + 1;
            Prev[i] = i / 3;
        }
    }

    // 최소 연산 횟수 출력
    cout << "최소 연산 횟수: " << dp[N] << endl;


    // 경로 추적
    vector<int> path;
    int current = N;
    while (current != 0) 
    {
        path.push_back(current);
        if (current == 1) break; // 1까지 왔으면 종료
        current = Prev[current];
    }


    // 경로 출력 (앞에서부터)
    cout << "연산 경로: ";
    for (int i = 0; i < path.size(); i++) 
    {
        if (i > 0) cout << " -> ";
        cout << path[i];
    }
    cout << endl;

    return 0;
}

 

 

3. 경로 추적

최소 연산 횟수뿐만 아니라, 실제 연산 경로를 알고 싶으면 Prev 배열을 활용하면 된다.

vector<int> path;
int current = N;
while (current != 0)
{
    path.push_back(current);
    if (current == 1) break;
    current = Prev[current];
}

• Prev 배열을 따라가며 1까지 이동하면 연산 경로를 얻을 수 있다.

 

 

4. 결과

예를 들어 N = 10일 때 두 방식 모두 결과는 같다.

 

Top-Down 실행 결과:

(Top-Down) 숫자를 입력하세요: 10
최소 연산 횟수: 3
연산 경로: 10 -> 9 -> 3 -> 1

 

Bottom-Up 실행 결과:

(Bottom-Up) 숫자를 입력하세요: 10
최소 연산 횟수: 3
연산 경로: 10 -> 9 -> 3 -> 1

두 방식 모두 최소 연산 횟수는 3이며, 경로는 10 → 9 → 3 → 1

 

 

 

5. 정리

위에서 구현한 문제처럼, DP를 활용하면 중복 계산을 줄이고 효율적으로 문제 해결이 가능하다..! 

• Top-Down은 재귀적 직관적 구현,
• Bottom-Up은 반복문으로 빠르고 안정적

기준	Top-Down	Bottom-Up
구현 난이도	쉬움 (직관적)	약간 어려움
코드 가독성	좋음	보통
실행 속도	보통	빠름
스택 위험	있음	없음
상태 일부만 필요	👍	❌
상태 전부 필요	❌	👍
대회/실전	△	👍

 

 

5-1. 추천 순서

1. Top-Down으로 점화식부터 떠올린다
2. 상태 범위 & 크기 확인
3. 범위가 크거나 전부 필요하면 → Bottom-Up으로 변환

실제로 구현할 때, 이 생각 흐름이 많이 사용된다고 한다

 

“생각은 Top-Down, 구현은 Bottom-Up”