백준 #31876 자존심 강한 두 천재의 대결

문제 링크

[31876 자존심 강한 두 천재의 대결]

문제 설명

길이가 같은 u진법으로 나타낸수와 v진법으로 나타낸 수가 수어질 때 두 수가 같은지 비교하는 문제

코드

import sys
input = sys.stdin.readline


u, v = map(int, input().split())
A = input().rstrip()
B = input().rstrip()
N = len(A)
if N >= 22:
    if u > v:
        print("ras")
    elif u < v:
        print("auq")
    else:
        if A > B:
            print("ras")
        elif A < B:
            print("auq")
        else:
            print("rasauq")
else:
    a = int(A, u)
    b = int(B, v)
    if a > b:
        print("ras")
    elif b > a:
        print("auq")
    else:
        print("rasauq")

풀이

두 수를 10진법으로 바꿔서 비교하면 시간초과가 발생한다. $u$와 $v$의 범위가 2부터 10사이이기 때문에 과연 몇자리수부터 10진법이 9진법으로 나타낼 수 있는 가장 큰 수보다 항상 커지는지 생각하면 되는 문제였다. 즉

\[10^n \gt 9*9^n+9*9^{n-1} + \dots + 9\]

를 만족하는 $n$의 범위를 구하면 되고 $n>21$이 나오기 때문에 21보다 큰 경우에는 진법이 큰 쪽이 무조건 크게되고 21이하의 경우에는 직접 각각의 진법을 10진법으로 바꿔서 비교해주면된다

풀면서 오랜만에 등비수열 합공식도 다시 유도해보아서 좋았고 이런 문제를 만드는 사람도 대단하다는 생각이 들었다..!