백준 Silver 2 A to B

A to B (백준 Silver 2)

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

A -> B로 향하는 값을 구하는 문제이다
이 문제의 특이한 사안은

1. A -> B로 향하는 ‘최소’ 연산 횟수 구하기
2. 그 연산들은 전부 A 값을 ‘증가시킴’

따라서
두 연산인
‘A * 2’ 와 ‘A * 10 + 1’ 중
후자가 더 A 값을 빠르게 증가시키므로
해당 값을 우선적으로 계산하는 쪽으로 잡았다

이후 재귀를 통하여 종료조건들을 설정하였는데

• a > b 보다 큰 경우, 탐색 실패
  
• 현재 탐색 결과가 최소 탐색 결과보다 크면, 탐색 실패
  
• a == b 이고, 현재 탐색 결과가 최소값이면 탐색 성공하며 값 갱신
  

으로 설정하고 재귀를 돌렸다

실패한 이유?

개인적으로 접근 방식은 괜찮았다고 생각하였는데
실패가 떴다

문제를 다시 읽어보니
A와 B가 int의 범위를 넘어보였다
(-2.147483648 × 10^9 ~ +2.147483647 × 10^9)
따라서 *10을 연산하는 중
오버플로우가 발생할 가능성이 있어보였으므로
그냥 unsinged long long 으로 바꾸고 실행하였다

잘 성공한 모습이다!

• 아마 long으로 해도 성공할 듯 하다
  
• 혹시 이러한 문제 계열 중 unsinged long long 으로 했는데 실패한다면
  문자열을 이용한 숫자 계산을 해야 하기에 난이도가 올라간다
  

그리디인 이유?

일단 문제를 재귀적으로 풀 수 있다는 점에서
‘최적 부분 구조’를 가진다
(하위 문제의 답을 모아 큰 문제의 정답을 만든다)

동시에 ‘현재’의 최선의 선택이 ‘결과적’으로 최선의 선택이 된다
*2보다 *10 + 1이 더 큰 값을 만들 수 있으므로
*10 + 1을 먼저 선택하는 것이 더 연산을 적게 함!
=> 그리디하다

제출 코드

#include<iostream>
#include<limits.h>

using namespace std;

typedef unsigned long long ull;

ull maxCount = LONG_MAX;

void recur(ull a, ull b, ull nowCount)
{
	if (a > b)
		return;

	if (nowCount > maxCount)
		return;

	if (a == b)
	{
		maxCount = nowCount;
		return;
	}

	recur(a * 10 + 1, b, nowCount + 1);
	recur(a * 2, b, nowCount + 1);
}

int main()
{
	ull a, b;
	cin >> a >> b;

	recur(a, b,0);

	if (maxCount != LONG_MAX)
		cout << maxCount + 1;
	else
		cout << -1;
}