취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14370번 문제인 Close Match (Large)이다.
문제는 아래 링크를 확인하자.

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

주어지는 두 수의 앞자리부터 순서대로 비교해나가며 문제를 해결해보자.

현재 살피고 있는 자리가 두 수 모두 '?'가 아닌 경우를 먼저 살펴보자.

두 수가 다를 경우 그 자릿수가 더 큰 수가 항상 더 큰 수가 되고 더 작은 수가 항상 더 작은 수가 된다. 따라서 큰 수의 남은 '?'자리를 0으로 채우고 작은 수의 남은 자리를 9로 채우는 것으로 답을 구해낼 수 있다.

두 수가 같을 경우, 다음 자릿수로 넘어가 새로 비교를 시작하자.

현재 살피고 있는 자리중 정확히 하나의 수만 '?'인 경우를 살펴보자.

이 때 '?'는 다른 알고 있는수와 같거나, 1만큼 크거나, 1만큼 작을 수밖에 없다. 크거나 작은 수로 결정할 경우 그 경우의 최선의 경우는 위에서 살핀 방법과 동일하게 찾아낼 수 있다. 두 수를 같게 잡았을 때의 최선의 경우는 다음 자릿수로 넘어가 새로 비교를 시작해 구하자.

현재 살피고 있는 자리가 둘 다 '?'인 경우를 살펴보자.

이 때 두 '?'는 0과 0, 0과 1, 1과 0 세가지의 경우중 하나이다. 0과 0일 경우에는 다음 자릿수로 넘어가 새로 비교해 최선의 경우를 구하고, 그 외의 경우 첫번째 경우와 같이 생각해 각각의 시도에 대하여 최선의 경우를 구해내보자.

위와 같은 시도를 하여 나오는 값 중 두 수의 차가 최소이면서 그중 첫번째 수가 최소가 되고 그 중 두번째 수가 최소가 되는 경우를 찾아 출력해주자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;

int slen;
pair<ll, ll> ans;

bool comp(pair<ll, ll>& p1, pair<ll, ll>& p2) {
	return abs(p1.first - p1.second) < abs(p2.first - p2.second);
}

void func(int idx, string s1, string s2) { 
	while (idx + 1 < slen && s1[idx] == s2[idx] && s1[idx + 1] == s2[idx + 1]) {
		if (s1[idx] == '?') s1[idx] = s2[idx] = '0';
		idx++;
	}

	if (idx == slen) {
		pair<ll, ll> p = make_pair(stoll(s1), stoll(s2));
		if (comp(p, ans)) ans = p;
	}
	else {
		if (s1[idx] != '?' && s2[idx] != '?') {
			if (s1[idx] < s2[idx]) {
				for (int i = idx; i < slen; i++) {
					if (s1[i] == '?') s1[i] = '9';
				}
				for (int i = idx; i < slen; i++) {
					if (s2[i] == '?') s2[i] = '0';
				}
				pair<ll, ll> p = make_pair(stoll(s1), stoll(s2));
				if (comp(p, ans)) ans = p;
			}
			else if (s1[idx] > s2[idx]) {
				for (int i = idx; i < slen; i++) {
					if (s2[i] == '?') s2[i] = '9';
				}
				for (int i = idx; i < slen; i++) {
					if (s1[i] == '?') s1[i] = '0';
				}
				pair<ll, ll> p = make_pair(stoll(s1), stoll(s2));
				if (comp(p, ans)) ans = p;
			}
			else func(idx + 1, s1, s2);
		}
		else if (s2[idx] != '?') {
			string tmp1 = s1;
			if (s2[idx] != '0') {
				tmp1[idx] = s2[idx] - 1;
				func(idx, tmp1, s2);
			}
			tmp1[idx] = s2[idx];
			func(idx + 1, tmp1, s2);
			if (s2[idx] != '9') {
				tmp1[idx] = s2[idx] + 1;
				func(idx, tmp1, s2);
			}
		}
		else if (s1[idx] != '?') {
			string tmp2 = s2;
			if (s1[idx] != '0') {
				tmp2[idx] = s1[idx] - 1;
				func(idx, s1, tmp2);
			}
			tmp2[idx] = s1[idx];
			func(idx + 1, s1, tmp2);
			if (s1[idx] != '9') {
				tmp2[idx] = s1[idx] + 1;
				func(idx, s1, tmp2);
			}
		}
		else {
			string tmp1 = s1, tmp2 = s2;
			tmp1[idx] = '0', tmp2[idx] = '0';
			func(idx + 1, tmp1, tmp2);
			tmp1[idx] = '0', tmp2[idx] = '1';
			func(idx, tmp1, tmp2);
			tmp1[idx] = '1', tmp2[idx] = '0';
			func(idx, tmp1, tmp2);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	for (int t = 1; t <= T; t++) {
		ans.first = 1000000000000000007LL, ans.second = 0;
		string s1, s2; cin >> s1 >> s2;
		slen = s1.length();
		func(0, s1, s2);
		
		string ss1 = to_string(ans.first), ss2 = to_string(ans.second);
		cout << "Case #" << t << ": ";
		for (int i = ss1.length(); i < slen; i++) cout << 0;
		cout << ss1 << ' ';
		for (int i = ss2.length(); i < slen; i++) cout << 0;
		cout << ss2 << '\n';
	}
}