취미로 코딩하기

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

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

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

14372번 문제(링크)에서 입력의 크기가 작아진 문제이다. 해당 문제의 풀이를 참고하여 문제를 해결하자.

입력의 크기가 작으므로, 모든 ?에 가능한 경우(0부터 9까지의 각 자릿수)를 대입하는 브루트포스를 통해서도 문제를 해결해 볼 수 있을 것이다.

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

#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';
	}
}