숫자 변환하기

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

 

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

 

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

 

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

---

문제 해설

 

DFS와 BFS 둘다 사용할 수 있는 문제이다.

 

x에 n을 더하는것,

x에 2를 곱하는것,

x에 3을 곱하는것,

 

의 3가지 경우를 깊이우선탐색, 너비우선탐색으로 돌리고 경우의수가 나타났을 때 종료하면 된다.

 

DFS의 경우는 제귀를 사용하고

BFS의 경우는 queue와 hash_map또는hash_set을 사용한다.

 

단!, DFS는 시간초과로 실패하는 경우가 있음으로 가능한 BFS로 실행할것.

---

첫 번째 시도

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int x, int y, int n) {
    queue<vector<int>> count;
    count.push({ x, 0 });
    while (!count.empty() && count.front()[0] != y)
    {
        vector<int> now = count.front();
        count.pop();
        if (now[0] * 2 <= y) count.push({now[0] * 2, now[1]+1});
        if (now[0] * 3 <= y) count.push({now[0] * 3, now[1]+1});
        if (now[0] + n <= y) count.push({now[0] + n, now[1]+1});                     
    }
    if (count.empty()) return -1;
    return count.front()[1];
}

실패

 

BFS형태로 시도하였으나 실패하였다, 정방향으로 x값을 중첩시켜서 나아가는 형태로 구상하였으나, 중첩된 경우의 수가 나타날 수 있음으로 그걸 고려하지 못했다.

 

또한, 곱셈으로 나타나게 되면 결국 최종적으로 도착하지 못하는 경우를 예측하지 못한다.

 

예를들어, y를 3으로 나누었을 때, x로 도달해야 하는데, 3으로 나누었을 때 나머지값이 나타나거나,

2로 나누었을 때 x로 도달해야 하는데 2로 나누었을 떄 나머지값이 나타나면 결국 도달하지 못한다고 볼 수 있다.

 

그럼으로, 정방향으로 접근하는것 보다 역방향으로 접근하는게 더효율적이다.

 

---

두 번째 시도

#include <string>
#include <vector>
#include <set>

using namespace std;

set<int> chack;

void DFS(const int& x, int y, const int& n, int count = 0)
{
    if (!chack.empty() && *chack.begin() < count) return;
    if ((y / 3) * 3 == y && y / 3 >= x)
        DFS(x, y / 3, n, count+1);
    if ((y / 2) * 2 == y && y / 2 >= x)
        DFS(x, y / 2, n, count + 1);
    if (y - n >= x)
        DFS(x, y - n, n, count + 1);
    if (y == x)
        chack.insert(count);
}

int solution(int x, int y, int n) 
{
    DFS(x, y, n);
    if (chack.empty()) return -1;
    return *chack.begin();
}

실패

 

깊이우선탐색으로 역방향 접근을 진행하였다.

 

접근방법이 옳고, 정답이 나타나나 11번 문항이 시간초과가 나타난다. 즉, 중첩된 연산값을 제외해야한다는 뜻.

 

해당 접근방식을 고려하여 DFS가 아니라 BFS가 유효함을 이해할 수 있다.

---

세 번째 시도

#include <string>
#include <vector>
#include <set>
#include <queue>
#include <unordered_set>

int solution(int x, int y, int n) {
    std::queue<std::pair<int, int>> q;
    std::unordered_set<int> visited;

    q.push({y, 0});
    visited.insert(y);

    while (!q.empty()) {
        int current = q.front().first;
        int count = q.front().second;
        q.pop();

        if (current == x) {
            return count;
        }

        if (current % 3 == 0 && current / 3 >= x && visited.find(current / 3) == visited.end()) {
            q.push({current / 3, count + 1});
            visited.insert(current / 3);
        }
        if (current % 2 == 0 && current / 2 >= x && visited.find(current / 2) == visited.end()) {
            q.push({current / 2, count + 1});
            visited.insert(current / 2);
        }
        if (current - n >= x && visited.find(current - n) == visited.end()) {
            q.push({current - n, count + 1});
            visited.insert(current - n);
        }
    }

    return -1;
}

성공

 

BFS형태의 접근방법을 고려하였다.

 

중첩연산을 생각해서, 전에 접근하였던 int값이라면, 이미 접근하였었음으로 다시한번 생성할 필요가 없기 때문에 제외하고.

 

역순으로 접근하여 나누었을 때, 나머지값이 0이 나타나야 하기 때문에 나머지값이 0이 아니라면 결과가 나타날 수 없어, 고려하지 않는다.

 

즉, 결괏값 에서 초기값으로 연산하는 과정에 연산했던 중복값을 처리하는걸 피하게 되면 성공한다.