백준 1463 1로만들기 - C++

문제 링크 : https://www.acmicpc.net/problem/1463


문제 설명

주어진 정수 X을 주어진 연산 방법으로 최소 몇 번의 연산으로 1로 만들 수 있는지를 구하는 문제이다.

문제의 조건은 이렇다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

위 조건으로 X를 1로 만든다면?

• 2를 1로 만드려면

  • 2 / 2 => 1 (연산 횟수 1)
  • 2 - 1 => 1 (연산 횟수 1)
    
    

• 4를 1로 만드려면

  • 4/ 2 - 1 => 1 (연산 횟수 2)

풀이

이 문제를 완전탐색을 통해 모든 경우의 수를 확인하여야 한다. 하지만 DFS / BFS로 문제를 구현하게 된다면 같은 수에 대한 연산이 여러번 수행되는 중복현상이 생겨 시간초과의 위험이 있어, 메모이제이션 기법을 적용해 다이나믹 프로그래밍으로 풀어주면 된다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1000001];

int main()
{
    
    int x;
    cin >> x;
    dp[1] = 0;

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

        if (i % 3 == 0)
        {
            dp[i] = min(dp[i / 3] + 1,dp[i]);
        }
        if (i % 2 == 0)
        {
            dp[i] = min(dp[i / 2] + 1,dp[i]);
        }
    }
    cout << dp[x];
    return 0;
}