[BOJ_C++] 1463번 : 1로 만들기

# 문제

---

# 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;
int d[1000001] = { 0, 0, 1, 1 };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;

    cin >> n;
    for (int j = 4; j <= n; j++) {
        d[j] = d[j - 1] + 1;
        if (j % 2 == 0 && d[j] > d[j / 2] + 1)
            d[j] = d[j / 2] + 1;
        if (j % 3 == 0 && d[j] > d[j / 3] + 1)
            d[j] = d[j / 3] + 1;
    }
    printf("%d\n", d[n]);
    
    return 0;
}

• 1에서 3은 이미 값이 정해져 있기 때문에 배열에 값을 넣어줬다.
• 처음 n의 값을 구할 때 가장 쉽게 알 수 있는 방법은 3번 1을 빼서 앞에서 미리 구해 놓은 값을 사용하는 방법이다.
• 이후 만약 2로 나누어 떨어지고 d[j]의 값보다 d[j/2]의 값에 1을 더한 값이 작다면 방법 2를 사용하였을 때 더 적게 연산하는 것이기 때문에 d[j]의 값을 d[j/2]+1로 바꿔준다.
• 만약 3으로 나누어 떨어진다면 방법2와 동일한 의미로 d[j]의 값을 d[j/3]+1로 바꿔준다.
• 최종적으로 구해진 d[n]을 출력하고 프로그램을 종료한다.

---

# 결과