백준 16953번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초	512MB	실버 2

 

---

풀이1

이 문제는 정말 생각할 수 있는 부분이 많은 좋은 문제라고 생각한다.

 

일단 문제를 보고 바로 든 생각은 그래프 문제구나 싶었다. 실제로 두 과정을 통해 a를 b로 만드는 최소 연산 횟수 + 1(a에서 b로 이동하는 최단경로)을 구하는 것이기 때문이다. a, b의 최댓값이 10^9로 약 2^30에 근접하고, 두 연산이 모두 곱하거나(2x), 곱하고 더하는 연산(10x + 1)이기 때문에 아무리 큰 케이스를 주더라도 연산은 30번에 근접할 것이다. 그리고, 나름의 최적화를 시도하여 큰 값부터 우선 처리하면, 더 빠르게 구할 수 있을거라고 생각하여 우선순위큐를 사용하여 bfs를 작성했다. 또한 a와 b가 모두 10억(10^9)이하라고 방심하고 int를 사용했다가 틀렸다. a와 b가 대략 2.2억 이상이라면 10을 곱하는 과정에서 int를 벗어날 수 있기 때문이다.

코드1

#include <bits/stdc++.h>
using ll = int64_t;
using namespace std;

ll a, b;

void sol() {
	ll ans = -1;
	priority_queue<pair<ll, ll>> pq;
	pq.push({a * 2, 2});
	pq.push({a * 10 + 1, 2});

	while(!pq.empty()) {
		auto [cur, cnt] = pq.top();
		pq.pop();

		if (cur == b) {
			if (ans == -1) ans = cnt;
			else ans = min(ans, cnt);
			break;
		}
		else if (cur < b){
			pq.push({cur * 2, cnt + 1});
			pq.push({cur * 10 + 1, cnt + 1});
		}
		else {
			continue;
		}
	}

	cout << ans;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> a >> b;
	sol();
}

풀이2

해당 문제를 풀고 나서 질문게시판을 훑어보며 많은 것을 배울 수 있었다. 이런 류의 문제는 같은 값을 여러번 탐색하는 경우를 유의해야하는데, 결론부터 말하면 해당 문제의 조건으로는 같은 값이 나올 수 없다. 이제부터 이를 간략하게 증명해나가보자.

 

b에 도달하기 위한 여러 방법이 있다면, 같은 숫자를 만드는데 다른 조합을 쓰더라도 만들 수 있어야만 한다. 하지만 2를 곱하는 것(P작업)은 짝수를 만들어내고, 뒤에 1을 추가하는 것(Q작업)은 홀수를 만들어내는 작업이다. 다음과 같은 경우의 수가 만들어진다.

 

• b가 1의자리가 1인 홀수라면 이는 반드시 이전 숫자에서 Q작업을 했다는 뜻이 되며, P작업으로는 해당 숫자를 만들어낼 수 없다.
• 반대로 b가 짝수라면 이는 반드시 이전 숫자에서 P작업을 했다는 뜻이며, Q작업으로는 해당 숫자를 만들어 낼 수 없다
• P작업이던 Q작업이던 어쨌든 b가 작업을 거치기 이전의 숫자가 1의자리가 1인 홀수/짝수인 경우에도 P,Q작업은 하나로 결정된다.

이는 다음과 같은 결론을 만들 수 있다.

다른 조건을 조합해도 같은 값은 나올 수 없으며,
이는 a -> b로 가는 루트는 유일하다.

 

 

여기서 내 풀이를 개선하는 방법과 다른 풀이가 나오게 된다.

 

제일 첫 풀이는 bfs에 우선순위큐를 쓰는 방법이었지만, a->b로 가는 루트가 유일하다면 dfs로 간단하게 작성이 가능해진다. 유일한 루트이므로, 그 루트는 곧 최소 연산 횟수가 된다. 물론 bfs도 얼마든지 가능하다.

코드2

#include <bits/stdc++.h>
using ll = int64_t;
using namespace std;

ll a, b;

int dfs(ll st, int cnt) {
	if (st > b) return -1;
	if (st == b) return cnt;

	return max(dfs(st * 2, cnt+1), dfs(10 * st + 1, cnt+1));
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> a >> b;
	cout << dfs(a, 1);
}

 

다른 풀이는 a->b로 가는 루트가 유일함을 보일때 쓴 방법을 그대로 사용하여 a->b를 만드는게 아니라 b->a를 그리디하게 작성하는 것이다.

코드3

#include <bits/stdc++.h>
using namespace std;

int a, b;

void sol() {
	int ans = 1;
	while (b > a) {
		if (b % 2 == 0) {
			b /= 2;
		}
		else if (b % 10 == 1) {
			b /= 10;
		}
		else {
			break;
		}

		++ans;
	}
	if (b == a) {
		cout << ans;
	}
	else {
		cout << -1;
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> a >> b;
	sol();
}

 

나름대로 최적화에 성공했다고 생각한 첫 풀이였지만 사실은 발적화였다는 사실이 좀 슬프긴 했지만... 뭐 어떤가 실패에서 배워나가는 것이니까