[C++] 백준 1463번 - 1로 만들기

---

0. 문제

 

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

1. 아이디어

 

1) 정수 N의 연산 횟수의 최솟값은 이전 값(N/2 or N/3 or N-1 중 최솟값)의 연산횟수에 +1한 값이 된다.

 

2. 소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
    std::vector<int> v;
    int N;
    std::cin >> N;
    v.resize(N + 1, -1);
    v[0] = v[1] = 0;
    for (int i = 2; i <= N; i++)
    {
        v[i] = v[i - 1] + 1;
        if (i % 2==0) v[i] = std::min(v[i / 2] + 1, v[i]);
        if (i % 3==0) v[i] = std::min(v[i / 3] + 1, v[i]);
    }
    std::cout << v[N];
} // 반복문을 이용한 구현
 
/*
std::vector<int> v;
    int makeOne(int N)
    {
        if (N == 1) return 0;
        if (v[N] != -1) return v[N];
 
        v[N] = makeOne(N - 1) + 1;
        if (N % 2 == 0)
            v[N] = std::min(makeOne(N / 2) + 1, v[N]);
        if (N % 3 == 0)
            v[N] = std::min(makeOne(N / 3) + 1, v[N]);
        return v[N];
    }
int main()
{
    int N;
    std::cin >> N;
    v.resize(N + 1, -1);
    std::cout << makeOne(N);
} // 재귀함수를 이용한 
*/

 

3. 결과

 

4. 피드백

 

• DP와 분할정복은 다르다. DP의 핵심은 이전에 계산된 값이 반복해서 다시 사용된다는 것! (그래서 따로 저장해둠)
• 재귀함수를 이용했을 때 메모리를 왜 저렇게 많이 잡아먹을까.. 

---