⭐️ 백준 1463번 문제 소개

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

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

⭐️ 문제 풀어보기

연산 방법은 총 3가지가 있다.
(1) N-1
(2) N/2 (나누어 떨어질 때)
(3) N/3 (나누어 떨어질 때)
이 3가지 방법으로 주어진 N을 1로 만들면 된다.
총 연산의 횟수가 가장 작아야 한다.

☝️ 점화식 생각해보기

N을 1부터 예를 들어 보면..
N = 1 라면 원하는 목표 1이니 연산이 0번 이루어진다.
N = 2 라면 N-1 연산이나 N/2 연산으로 목표 1을 만들 수 있어 최소 연산이 1번이다.
N = 3 라면 N-1 연산 후 N/2 연산을 하여 목표 1을 만들 수 있지만 연산 횟수가 2번이다.
반면, N/3 연산으로 목표 1을 만들 수 있어 최소 연산이 1번이다.

N이 1, 2, 3일 때의 최소 연산은 구해졌다. 그렇다면 N = 4 라면?
N = 4 라면 N/2 연산을 하면 N = 2가 된다. N = 2일 때는 앞서 N = 2일 때 구해둔 최소 연산이 1번을 알 수 있다. 총 최소 연산은 (N/2연산 1번) + (N=2 일 때 최소 연산 1번) = 2번이다.
이렇게 앞에 구해둔 최소 연산이 DP 배열에 있으면 그 값을 찾아서 더하면 된다.

✌️ DP 만들기

앞서 구한 내용을 바탕으로 DP 배열을 만들어보자.
DP 배열에는 우리가 원하는 결과값을 저장한다.
N = 1일 때 최소 연산이 0번이니 DP[1] = 0
N = 2일 때 최소 연산이 1번이니 DP[2] = 1
N = 3일 때 최소 연산이 1번이니 DP[3] = 1
N = 4일 때 N/2 연산 이후 N=2일 때 구해둔 연산과 더한다. DP[2] + 1 = 1 + 1 = 2

🤟 코드로 나타내기

결국 N을 1로 만들기 위해서는
N-1은 연산 횟수 1번
N/2은 연산 횟수 1번
N/3은 연산 횟수 1번이므로
한번의 연산을 거치면 +1을 해주면 된다. 이를 코드로 나타내면..
DP[N] = DP[N-1] + 1 (연산 횟수 +1)
DP[N] = DP[N/2] + 1 (연산 횟수 +1)
DP[N] = DP[N/3] + 1 (연산 횟수 +1) 이렇게 된다.
이 세 개 중 가장 작은 값을 DP에 저장해야 한다.

예를 들어, DP[4]가 있다면
DP[4-1] + 1, DP[4/2]+1, DP[4/3] + 1 중 가장 작은 것을 찾는다.
DP[3] + 1 = 1 + 1 = 2
DP[4/2] + 1 = DP[2] + 1 = 1 +1 = 2
DP[4/3] + 1 -> 나누어 지지 않음
따라서 2가 가장 작음을 알 수 있다. DP[4] = 2로 갱신한다.

이 부분을 코드로 나타내면 다음과 같다.

dp[1] = 0; 
for(int i=2; i<=N; i++){
	// N-1 연산 
	dp[i] = dp[i-1] + 1; 
    
    // N-1 연산과 N/2 연산 중 더 작은 것 선택
    if(i%2 == 0) dp[i] = min(dp[i]. dp[i/2] + 1);
    
    // N-1 연산과 N/3 연산 중 더 작은 것 선택
    if(i%3 == 0) dp[i] = min(dp[i], dp[i/3] + 1);
    // 둘 중에 아무것도 나누어 지지 않았다면 N-1 연산 선택
}

전체 코드를 보면 다음과 같다.

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

int main() {
    int n;
    cin >> n;
    
	vector<int> dp;
    dp.assign(n+1, -1);
    dp[1] = 0;

    for(int i=2; i<=n; i++){
        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);
    }

    cout << dp[n] << endl;

    return 0;
}