[ARC142 A] Reverse and Minimize

난이도: 552

 

태그

• Mathematics
• Reversal

 

풀이

1. 뒤집기 연산의 특징

문자열을 뒤집는다고 생각해봅시다.

그럼, 2번 뒤집으면 원래대로 돌아온다는 건 자명합니다.

 

그런데, 이번에는 수를 뒤집기 때문에, 그리고 그 뒤에 Leading Zero를 삭제하기 때문에

2번 뒤집는다고 항상 원래대로 돌아오진 않을 수 있습니다.

 

하지만, 조금 더 나아가볼까요?

어떤 수는, 그 초기 상태만으로도 Leading Zero가 존재하지 않습니다.

1번 뒤집으면, Leading Zero와 Trailing Zero가 존재하지 않습니다.

// Trailing은 원래 Leading이 없었으니 존재하지 않고, Leading은 삭제되죠.

2번 뒤집어도, Leading Zero와 Trailing Zero가 존재하지 않습니다.

3번 뒤집어도, 4번 뒤집어도 이는 계속 유지됩니다.

 

그리고, Leading Zero와 Trailing Zero가 없는 수는 문자열의 뒤집기와 정확히 동일하게 작용하기 때문에

그 시점부터는 2번 뒤집으면 원상복귀한다는 성질이 성립합니다.

 

2. [1]을 토대로, \( K \)를 최솟값으로 가지는 것이 경우는?

만약 \( K \)에 Trailing Zero가 들어있다면, \( f(K) \) 의 길이가 \( K \)보다 짧아지므로, 자명히 \( f(K) < K \)가 되어 \( K \)를 최솟값으로 가질 수 없습니다.

 

그러니, 지금부터는 Trailing Zero가 없다고 가정해봅시다.

이 때부터는 \( f(f(K)) = K \)가 성립하므로, \( K \)와 \( f(K) \) 간의 비교만 하면 됩니다.

즉, 만약 \( f(K) < K \)였다면 불가능하고, \( f(K) \ge K \)라면 가능합니다.

 

3. 가능한 경우, 무슨 수들이 가능할까?

우선, \( K \)가 가능합니다.

[2]를 통과한 모든 \( K \)에 대해 \( f(f(K)) = K \)이므로, \( f(K) \) 역시 가능합니다.

그 뒤로는, Trailing Zero를 붙이는 것 외에는 뒤집기로 만들어낼 수 있는 게 없습니다.

 

즉, 가능한 수들은 \( K, f(K), 10K, 10f(K), 100K, 100f(K), \ldots \)가 됩니다.

이 중 \( N \)보다 작은 수의 개수를 세주면 되겠죠.

 

4. 코드

ll rev(ll x){
    ll res = 0;
    while (x){ res = res*10 + x%10; x /= 10; }
    return res;
}
 
void Main(){
    ll n, k; cin >> n >> k;
    if (k%10 == 0){ cout << 0; return; }
    if (rev(k) < k){ cout << 0; return; }
    int ans = 0;
    ll x1 = k, x2 = rev(k);
    while (x1 <= n){
        ans += 1;
        if (x1 != x2 && x2 <= n){ ans += 1; }
        x1 *= 10; x2 *= 10;
    }
    cout << ans;
}