백준 1463번: 1로 만들기 / C++

1463번: 1로 만들기 (acmicpc.net)

1463번: 1로 만들기

---

처음 접근방법은 현재 입력값에서 한칸씩 내려가면서 찾을려고 했는데 실수한 부분이 낮은수와 높은 수를 비교할때 낮은 수의 경우에만 계산했기때문에 문제를 해결하지 못했다. 그래서 이번에는 반대로 역순으로 배열을 만들어서 문제를 해결하였다.

 
#include <iostream>
#include <vector>
 
using namespace std;
 
int arr[1000001] = { 0, 0, 0, 0};
 
int main()
{
    int num = 0;
    cin >> num;
    vector<int> vec;
    vec.push_back(1);
    int i = 1;
    if (num != 1)
    {
        while (arr[num] == 0)
        {
            vector<int> vec2;
            for (auto iter = vec.begin(); iter != vec.end(); ++iter)
            {
                int X = *iter;
                if (2 * X < 1000001 &&arr[2 * X] == 0)
                {
                    arr[2 * X] = i;
                    vec2.push_back(2 * X);
                }
                if (3 * X < 1000001 && arr[3 * X] == 0)
                {
                    arr[3 * X] = i;
                    vec2.push_back(3 * X);
                }
                if (X + 1 < 1000001 && arr[X + 1] == 0)
                {
                    arr[X + 1] = i;
                    vec2.push_back(X + 1);
                }
            }
            vec.clear();
            vec = vec2;
            ++i;
        }
    }
 
    cout << arr[num];
 
    return 0;
}