BOJ 1078 | 뒤집음

요약 : 코딩을 못해도 시간을 박으면 누구나 풀 수 있다. 근성으로 가능한 플레 I 문제다! 근데 오래 걸린다.

완전 수학 문제였는데 예제 입력과 출력이 잘 나와 있어서 풀기까지 시간은 많이 걸렸지만 틀렸습니다를 받진 않았다.

교양 시간에 풀기 시작했는데 중간에 너무 많은 정보와 가정들이 머릿속에서 뒤엉켜서 뇌정지가 와버렸다.

관찰한 특징을 잘 솎아내서 정제된 풀이과정으로 만드는 작업이 심히 어려웠던 문제가 되겠다.

$D$가 1,000,000까지밖에 되지 않아 완전탐색으로도 풀릴까 했지만 $x$는 $10^{13}$ 까지 올라간다는 사실을 깨닫고 절망했다.

먼저 $X - \bar{X}=D$인 $X$가 존재하기 위한 조건을 알아보자.
참고로 $\bar{X}$는 $reversed(X)$이다.

$X$ = $7654321$ 일 때, $X-\bar{X} = 7654321-1234567$이다.

즉, $X$의 모든 자릿수에 대해 같은 숫자가 $\bar{X}$에 존재한다. (너무 당연하다) 그러므로 그 숫자끼리 묶을 수 있다.

$X-\bar{X} = (10^6-10^0)\times7 + (10^5-10^1)\times6+... + (10^1-10^5) \times 2 + (10^0-10^6) \times 1$

여기서 눈치챘겠지만 맨 앞의 항과 맨 뒤의 항은 $(10^6-10^0)$으로 묶을 수 있다. 2번째 항과 마지막에서 2번째 항도 그러하다. 이런 식으로 식을 정리하면 다음과 같이 나온다.

$X-\bar{X}=(10^6-10^0)\times(7-1)+(10^5-10^1) \times(6-2)+(10^4-10^2)\times(5-3)+(10^3-10^3)\times(4-4)$

이제 $(10^n-10^k)$ 형태에 주목하자. 이 형태의 식들은 하나의 공통점이 있는데, 바로 $9$로 나누어 떨어진다는 점이다. 그래서 $X-\bar{X}$는 항상 $9$의 배수가 된다.

$X-\bar{X}=999999\times(7-1)+99990\times(6-2)+9900\times(5-3)$

여기까지 알아낸 사실은 다음과 같다.

• $D$가 어떤 조건을 만족할 때만 $X-\bar{X}$ 형태로 나타낼 수 있다.
• $D$는 항상 $9$의 배수여야 한다.
• $X$의 자릿수를 $l$이라고 하면, 항이 $l/2$개인 식으로 $D$를 표현할 수 있다.

이제 $D/9$에 대해서 생각해 보자.

아까 들었던 예시인 $X=7654321$에 대해 $D/9$는 다음과 같다.

$D/9 = 111111\times6+11110\times4+1100\times2$

규칙성이 보이지 않는가?
항이 오른쪽으로 갈 수록 111111 => 11110 => 1100 으로 중요해보이는 숫자가 점점 줄어들고 있다.

세로로 한번 보자.

......$1100$ $\times\ 2$
...$11110$ $\times\ 4$
$111111$ $\times\ 6$

마치 1이 탑처럼 쌓인 형태가 된다.

만약 저 $2, 4, 6$을 몰라도 저 자리에 $2, 4, 6$이 들어간다는 사실을 충분히 유추할 수 있을까?

가능하다. 왜냐하면 우리는 이미 $D/9$ 값을 알고 있기 때문이다.

$D/9=713306$ 일 때, $111111$ 항만 가장 마지막 자릿수에 영향을 미치고, 그 부분을 계산해서 제하고 나면 $11110$ 항만 마지막에서 두 번째 자릿수에 영향을 미친다.
이런식으로 반복해나가면 $2, 4, 6$ 값이 들어가야 한다는 사실을 알 수 있다.

정리

$X$가 1자리 수일 때, $D/9$는 존재하지 않는다.
$X$가 2자리 수일 때, $D/9 = 1\times a$ 형태다.
$X$가 3자리 수일 때, $D/9 = 11\times a$ 형태다.
$X$가 4자리 수일 때, $D/9= 111\times a+10 \times b$ 형태다.
$X$가 5자리 수일 때, $D/9=1111 \times a+110 \times b$ 형태다.
$X$가 6자리 수일 때, $D/9=11111 \times a + 1110 \times b + 100 \times c$ 형태다.
$.$
$.$
$.$
$X$가 13자리 수일 때, $D/9 = 111111111111\times a + 11111111110 \times b + ... + 1100000 \times f$ 형태다.

이미 13자리 수에서 $D/9$가 표현 가능한 최솟값은 1,000,000을 넘어갔다. $D$의 최댓값이 1,000,000이므로 여기까지만 탐색해도 충분하다.

$D$에 대한 $X$가 n자리 수인지 확인하는 방법은 위에서 설명한대로 저 $D$를 표현하는 수식으로 입력된 $D$가 표현되는지 체크해 보면 된다.

탐색해야 할 분기가 13개밖에 안 되므로 그냥 하드코딩해도 되고, 조금 다듬어서 똑똑하게 풀어도 된다.

저 식에서 $a, b, c, d, ...$등의 해를 구했다면 거기서 파생되는 $X$는 하나가 아니라 여러 개가 나오는데, 그 중 최솟값이므로 $a$ 등이 양수라면 $(a, 0)$으로 두고, 0이라면 맨 앞 자릿수일 때는 $(1, 1)$, 아니면 $(0, 0)$, 음수라면 $(0, a)$로 두면 된다.

Comment

$D/9$로 정리해서 보기 전까지는 머릿속에서 떠오르는 여러 가짜 예외들이 생각을 방해했는데, $999999$로 보는 것 보다는 $111111$로 보는게 훨씬 깔끔하고 편했다.

이 문제를 처음 봤을 때는 쉬워 보였고, 풀다가는 꼬여버려서 포기하려고도 했지만 결국 풀고 나니 충분히 시간만 들여서 깊게 생각한다면 풀 수 있는 문제 같다.

문제의 존재 자체는 예전에 알고 있었지만 그 때는 그냥

친구에게 수학 관련 문제 추천해주려다가 떠오른 문제인데, 이번 기회에 풀게 되어서 기분이 좋다.

코드

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

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long

#define debug if constexpr (local) std::cout
#define endl '\n'

const ll macro[] = {0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111, 1111111111111, 11111111111111, 111111111111111, 1111111111111111, 11111111111111111, 111111111111111111, 1111111111111111111};
ll ipow(ll n, ll k){
	if (k == 0) return 1;
	
	if (k % 2) return n * ipow(n, k-1);
	return ipow(n, k/2) * ipow(n, k/2);
}

ll solve(ll len, ll D){
	ll x = 0;
	for (int i = 0; 2*i < len-1; i++){
		// last * 11...11
		int last = D % 10;
		
		ll minus = macro[len-1 - i*2] * last;
		//debug << "len " << len << " D " << D << " Minus " << minus << endl;
		
		D -= minus;
		D /= 10;
		
		if (i == 0 && last == 0){
			x += ipow(10, len-1 - i);
			x += ipow(10, i);
		}
		else if (minus > 0){
			x += ipow(10, len-1 - i) * abs(last);
		}
		else{
			x += ipow(10, i) * abs(last);
		}
		
	}
	
	if (D != 0) return -1;
	return x;
}

int main(){
	int D; cin >> D;
	
	if (D % 9){
		cout << -1; 
		return 0;
	}
	D /= 9;
	
	
	for (int i = 2; i < 12; i++){
		ll rst = solve(i, D);
		if (rst != -1){
			cout << rst;
			return 0;
		}
	}
	
	cout << -1;
}