급하게임개발

https://www.acmicpc.net/problem/16953

이 문제의 경우 사실 dfs로푸는게 간단해보였다 하지만 문제 분류가 그리디로 되어있었으니 그리디로 풀어 보겠다

이문제의 경우 A와 B가 주어졌을 경우 A에서 B를 만든다고 생각하지말고 B에서 A로 가야한다고 생각해야 잘풀리는 문제였다 B가 일단 2로 나누어지는 경우 2로 나누고 B가 10으로 나누었을 때 1이 남으면 10으로 나눈다 그후 A와 비교해서 같으면 나오고 아니면 다시 실행한다 단 B가 A보다 작아졌을 경우는 문제의 답이 존재하지 않는 경우기 때문에 -1을

출력한다.

이문제의 경우 상당히 쉬웠지만 계속 A에서 B를 만들려고 하니 시간이 많이 소모되었다.

#include <iostream>
using namespace std;
int main() {
	int A, B;
	int countnum=0;
	cin >> A >> B;
	while (true) {
		if (A == B) {
			countnum += 1;
			break;
		}
		if (A > B) {
			countnum= -1;
			break;
		}
		if (B % 10 == 1) {
			B--;
			B = B / 10;
			countnum++;
		}
		else if (B % 2 == 0) {
			B = B / 2;
			countnum++;
		}
		else {
			countnum= -1;
			break;
		}
	}
	cout << countnum;

}