1로만들기 (백준1463)

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

1463번: 1로 만들기

---

Dnamic Programming(동적계획법)은 메모이제이션 통해 중복계산값을 저장해 효율을 높여준다.

1) Python 이용

# DP --> 메모이제이션: 중복계산값을 줄여 효율 높여줌

n = int(input())

d = [0] * (n + 1) 
# d에 계산값 저장
# d[0] = 0, d[1] = 0

for i in range(2, n + 1):
    d[i] = d[i - 1] + 1
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)

print(d[n])

2) C 이용 (C 너무 오랜만이라 안까먹을려구,,,)

#include <stdio.h>
#include <stdlib.h>
#define min(x, y) ((x) < (y) ? (x) : (y))

int main()
{
    int n;
    scanf("%d", &n);
    int d[n + 1];
    d[0] = 0;
    d[1] = 0;
    for(int i = 2; i <= n + 1; i++)
    {
        d[i] = d[i - 1] + 1;
        if(i % 3 == 0) d[i] = min(d[i], d[(int)(i / 3)] + 1);
        if(i % 2 == 0) d[i] = min(d[i], d[(int)(i / 2)] + 1);
    }
    printf("%d", d[n]);
    
}

3) C++ 이용 (C++도 한번 배워보기,,,)

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

int d[10000001];

int main(){
    int n;
    
    cin >> n;

    for(int i = 2; i <= n; i++){
        d[i] = d[i - 1] + 1;
        if(i % 2 == 0) d[i] = min(d[i], d[i / 2] + 1);
        if(i % 3 == 0) d[i] = min(d[i], d[i / 3] + 1);
    }

    cout << d[n] << endl;

    return 0;
}