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

문제 설명

자연수 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

---

---

BFS를 활용하여 간단하게 풀 수 있는 문제이다.

 

	#include <string>
	#include <vector>
	#include <queue>
	using namespace std;
	typedef pair<int,int> point;
	bool vis[1000001];
	queue <point> q;
	int solution(int x, int y, int n) {
	int answer = 0;
	if(x == y) return 0;
	q.push(make_pair(x,0));
	while(!q.empty()){
	int cur = q.front().first;
	int curt = q.front().second;
	q.pop();
	if(cur + n <= y && !vis[cur + n]){
	vis[cur + n] = true;
	if(cur + n == y)
	return curt + 1;
	q.push(make_pair(cur + n ,curt + 1));
	}
	if(cur * 2 <= y && !vis[cur * 2]){
	vis[cur * 2] = true;
	if(cur * 2 == y)
	return curt + 1;
	q.push(make_pair(cur * 2 ,curt + 1));
	}
	if(cur * 3 <= y && !vis[cur * 3]){
	vis[cur * 3] = true;
	if(cur * 3 == y)
	return curt + 1;
	q.push(make_pair(cur * 3 ,curt + 1));
	}
	}
	return -1;
	}

view raw 숫자변환하기.cpp hosted with ❤ by GitHub

---

 

간단한 문제이다. 이것보다 어려운 문제를 풀어서 금방 생각이 났다. 하지만 한 테케가 틀렸는데 x 와 y가 같은 경우를 생각하지 못했다! 테케를 보자마자 생각이 났지만 테케를 보여주지 않았다면 보였을까..? 싶다