[백준(BOJ)] 1463번: 1로 만들기 (Dynamic Programming, C++)

💻 C++ 제출코드

---

#include <stdio.h>
#include <algorithm>
using namespace std;

int main(){
    int N;
    scanf("%d", &N);

    int DP[N];
    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);
    }
    printf("%d", DP[N]);
}

 

📝 문제풀이 과정

---

• 규칙을 찾아서 점화식을 만든다.
• 배열의 인덱스는 숫자, 숫자의 값은 세 개의 연산 최소로 숫자를 1로 만드는 최소 횟수
• DP[1] = 0 (1은 그냥 1이므로 연산 0번)
• N은 N-1에 1을 더하고, N/2에 2를 곱하고, N/3/에 3을 곱해서 구할 수 있다.
• DP[i] (현재 숫자의 연산횟수) = DP[i-1] + 1으로 정하고, i가 2로 나눠떨어지면 DP[i]와 DP[i/2] + 1에서 최솟값을, 3으로 나눠 떨어지면 DP[i], DP[i/3]+1에서 최솟값을 가져난다.

 

👏 결과

---