-
[프로그래머스] 숫자 변환하기 c++Coding Test/programmers 2023. 1. 27. 17:17728x90
문제 설명
자연수 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 풀이
#include <string> #include <vector> #include <queue> #include <set> using namespace std; void calculate(int num, int y,int n ,set<int>& hash, queue<int>& q){ if(num + n <= y && hash.count(num + n) == 0){ hash.insert(num+n); q.push(num+n); } if(num * 2 <= y && hash.count(num * 2) == 0){ hash.insert(num * 2); q.push(num * 2); } if(num * 3 <= y && hash.count(num * 3) == 0){ hash.insert(num * 3); q.push(num * 3); } return; } int solution(int x, int y, int n) { int answer = 0; queue<int> q; set<int> hash; q.push(x); while(!q.empty()){ int len = q.size(); for(int i = 0; i < len; i++){ if(q.front() == y){ return answer; } int nx = q.front(); q.pop(); calculate(nx, y, n, hash, q); } answer++; } return -1; }
다른 풀이2
#include <string> #include <vector> using namespace std; int dp[1000001]; int solution(int x, int y, int n) { int answer = 0; fill(dp, dp + 1000001, INT16_MAX); 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 == INT16_MAX){ answer = -1; } return answer; }
다른 풀이3
#include <string> #include <vector> #include <queue> using namespace std; int bfs(int x, int y, int n){ if(x == y){ return 0; } vector<bool> check(y+1, false); queue<int> q; q.push(x); int depth = 1; while(!q.empty()){ int len = q.size(); for(int i = 0; i < len; i++){ int now = q.front(); q.pop(); check[now] = true; int plus = now + n; int x2 = now * 2; int x3 = now * 3; if(plus == y || x2 == y || x3 == y){ return depth; } if(plus < y && !check[plus]){ q.push(plus); } if(x2 < y && !check[x2]){ q.push(x2); } if(x3 < y && !check[x3]){ q.push(x3); } } depth++; } return -1; } int solution(int x, int y, int n) { int answer = 0; answer = bfs(x, y, n); return answer; }
다른 풀이4
#include <string> #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 val = q.front().first; int cnt = q.front().second; q.pop(); if(val == x){ return cnt; } if(val % 2 == 0){ q.push(make_pair(val / 2 , cnt + 1)); } if(val % 3 == 0){ q.push(make_pair(val / 3, cnt + 1)); } if(val - n > 0){ q.push(make_pair(val - n, cnt + 1)); } } return -1; }
728x90'Coding Test > programmers' 카테고리의 다른 글
[프로그래머스] 주식가격 java c++ (0) 2023.01.28 [프로그래머스] 올바른 괄호 c++ (0) 2023.01.28 [프로그래머스] 뒤에 있는 큰 수 찾기 c++ (0) 2023.01.27 [프로그래머스] 무인도 여행 c++ (0) 2023.01.27 [프로그래머스] 거스름돈 c++ (0) 2023.01.26