[프로그래머스 C++] 숫자 변환하기

[프로그래머스 C++] 숫자 변환하기

 

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

---

 

해결방안

 

BFS

DP

---

 

처음 시도한 코드 - DFS 시간초과

 

#include <string>
#include <vector>
#include <climits>
using namespace std;

int answer=INT_MAX;
int cnt;

void DFS(int x, int y, int n, int cnt)
{
	if(x == y){
        answer = min(answer, cnt);
        return;
	}
    else if (x > y){
        return;
    }

    DFS(x + n, y, n, cnt+1);
    DFS(x * 2, y, n, cnt+1);
    DFS(x * 3, y, n, cnt+1);
}

int solution(int x, int y, int n) {

    DFS(x, y, n, 0);

    if (answer == INT_MAX) 
        answer = 0;

    return answer;
}

 

 

---

 

정답 코드 - BFS

 

#include <queue>
#include <vector>
using namespace std;

int solution(int x, int y, int n) {
    vector<int> visited(10001, -1); // 방문 체크 및 연산 횟수를 저장할 배열
    queue<int> q;

    visited[y] = 0; // 시작점의 연산 횟수는 0
    q.push(y);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        if (cur == x) // x에 도달한 경우
            return visited[cur];

        // 가능한 모든 연산을 수행
        if (cur - n >= 0 && visited[cur - n] == -1) {
            q.push(cur - n);
            visited[cur - n] = visited[cur] + 1;
        }
        if (cur % 2 == 0 && visited[cur / 2] == -1) {
            q.push(cur / 2);
            visited[cur / 2] = visited[cur] + 1;
        }
        if (cur % 3 == 0 && visited[cur / 3] == -1) {
            q.push(cur / 3);
            visited[cur / 3] = visited[cur] + 1;
        }
    }

    return -1; // x에 도달할 수 없는 경우
}

 

 

방문체크 생략 코드

#include <vector>
#include <queue>
using namespace std;

int solution(int x, int y, int n) 
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(y, 0));

    while (!Q.empty())
    {
        int k = Q.front().first;
        int cnt = Q.front().second;
        Q.pop();

        if (k == x)
            return cnt;

        if (k % 2 == 0)
        {
            Q.push(make_pair(k / 2, cnt + 1));
        }

        if (k % 3 == 0)
        {
            Q.push(make_pair(k / 3, cnt + 1));
        }

        if (k - n > 0)
        {
            Q.push(make_pair(k - n, cnt + 1));
        }
    }

    return -1;
}

  

 

---

 

정답 코드 - DP 

 

#include <string>
#include <vector>
#include <climits>
using namespace std;

vector<int> dp(1000001, INT_MAX); 

int solution(int x, int y, int n) {
    int answer = 0;
    
    dp[x] = 0;

    for(int i = x; i <= y; i++)
    {
        if(i+n <= y) dp[i+n] = min(dp[i+n], dp[i] + 1);
        if(i*2 <= y) dp[i*2] = min(dp[i*2], dp[i] + 1);
        if(i*3 <= y) dp[i*3] = min(dp[i*3], dp[i] + 1);
    }
    answer = dp[y];
    
    if(answer == INT_MAX) 
    	answer = -1;
        
    return answer;
}