[백준 - 106953] A → B

#include<iostream>
#include<string>

typedef unsigned int integer;
using namespace std;

int main()
{
	integer A, B;
	cin >> A >> B;

	integer cnt = 1;
	while (A <= B && B != 0)
	{
		if (A == B)
		{
			cout << cnt;
			return 0;
		}

		if (B % 10 == 1)
		{
			B /= 10;
		}
		//홀수 체크
		else if ((B & 0x1) == 0x1)
		{
			cout << -1;
			return 0;
		}
		else
		{
			B /= 2;
		}
		++cnt;
	}

	cout << -1;
	return 0;
}

---

||사고 과정

처음에 분명 각 *2를 하거나 1을 추가하는 특정 조건이 있을거라 생각했다.

그래서 언제 1이 추가될까 생각을 했는데 정말 규칙이 없었다.

 

생각하던중에 A를 계속 순서없이 계속 연산하면 규칙도 없고 경우의 수도 많기 때문에

미로처럼 거꾸로 찾으면 쉽지 않을까 생각해서

A →  B가 아닌 B →  A로 거꾸로 연산해보던 중에

마지막 자리가 1이 되는 순간  나눗셈은 불가능하고 무조건 1을 빼야하는 규칙을 찾았다.

 

---

||사용 기법

• 그리디

• 비트연산

---

||풀면서 느낀 것

• 무언가 그리디는 규칙이 딱딱 있는 느낌같다

규칙이 딱 정해져있어서 그냥 쭉 나아가다가 정답나오면 정답을 하는 느낌이다 =~=

• 그래프?

다 풀고나서 다른 사람들도 보니까 그래프로 푸는 사람들도 있던데

나도 처음에 그래프로 풀수 있는가? 생각은 해봤지만 전혀 아닌거 같아서 다른 방법을 찾았는데

역시 아직 그래프적 사고는 서툰듯하다 😪

• 정수 뒷자리 빼기

나는 처음에 뒷자리를 빼야해서 string으로 pop하는걸 생각했었는데

정수도 / 10 을 저장하면 뒷자리가 빠지더라..

이렇게 정수를 사칙연산으로 여러가지 응용 할 수 있는 방법도 생각해봐야겠다.

---

||나아 진것

• 잘했다

요즘 잘 못풀어서 자신감이 하락했었는데

푸는 과정자체가 잘 돌아갔던 문제로 전체적으로 초반보다 나아졌다고 생각한다