[SWEA/Python] 17643번 - 로봇

 

문제

SWEA 문제

 

[문제]

 

2차원 평면의 원점에서 로봇이 움직이기 시작하는데 특정 좌표(x,y)에 있을 가능성이 있는지 구하는 문제다.

특징은 로봇은 상하좌우 4방향으로 이동할 수 있고 t초마다 3^t 만큼 고른 방향으로 이동한다.

​

 

풀이

 

처음에는 DFS처럼 완전 탐색을 해서 풀려고 했지만 시간 초과가 떴다.

 

그래서 어떻게 다른 방법으로 풀 수 있을까 생각해봤다.

$$\frac{3^t}{2}>\sum_{n=0}^{t-1} 3n\quad (t\neq 0)$$​

그러던 중 위의 식이 항상 성립하는 것을 찾았는데, 쉽게 생각하면 a라는 수에 1/3을 계속 곱한 등비수열은 a/2에 수렴한다는게 떠올랐다.

 

그렇기 때문에 t=n일 때, t=(0 ~ n-1)까지의 수들로 최대 표현할 수 있는 수는 (3^n)//2 까지다.

​

위 논리에 의하면 t=(0 ~ n-1)의 수들로 (3^n)//2까지 모든 수를 표현할 수 있음을 알 수 있다.

 

​쉽게 예를 들면 t가 최대 1일때 0,1,2,3,4를 표현할 수 있다(0은 모든 수 사용 X).

 

만약 t가 최대 2라면 3^2=9이고, 앞에서 t가 최대 1일 때 3^0, 3^1으로 0,1,2,3,4를 표현하는게 가능했으므로 9에서 0,1,2,3,4를 빼면 5,6,7,8,9가 표현되고 더하면 10~13까지 표현할 수 있다. 13 == 27//2이다.

​

이 생각에서 착안해 어떠한 수 x가 3^t보다 작고, (3^t)//2+1 보다 크다면 3^t를 반드시 포함해야 된다는 사실을 알았다.

 

그래서 x, y좌표 중 절댓값이 큰 수(이하 큰 수 = max, 작은 수 = min)를 찾고 max보다 값이 큰 3^t(해당하는 t 중 가장 작은 t)를 찾았다.

 

이후 max가 (3^t)//2+1보다 크면 t를 그대로 두고 작거나 같으면 t에서 1을 뺐다.

 

그 다음 max의 절댓값에서 3^t를 빼고 t에서 1을 뺀 다음 다시 min과 비교해 절댓값이 큰 수를 찾아서 위 과정을 반복 했다.

​

[요약]

1.

$$3^{t-1}\leq left < \frac{3^t}{2}+1 \leq {right} < 3^t$$​

$$3^{t-1}\le \ left\ <\frac{3^t}{2}+1\le \ right\ <3^t$3t−1≤ left <3t2​+1≤ right <3t$$​

에서 큰 수가 어느 범위에 있는지 찾는다. (left에 있으면 3^t를 포함 X, right에 있으면 3^t를 포함 O)

​

2.

$$\frac{3^{t-2}}{2}+1< {small} \leq 3^{t-1} \leq {big} < \frac{3^t}{2}+1$$​ ​

3^t로 이루어진 수는 무조건 한번은 사용해야 하므로 max가 small과 big 범위에 있으면 빼고 없으면 break 하면 된다.

 

 

Code

 

 

# 3의 제곱수로 모든 수 표현이 가능함.
for tc in range(int(input())):
    # visited=[False]*25 # 대충 이정도면 10**9
    x,y=map(int,input().split())
    max_n,min_n=max(abs(x),abs(y)),min(abs(x),abs(y))
    t=0
    while 3**t < max_n:
        t+=1 # t가 가질 수 있는 최대 지수값
    if max_n<=(3**t)//2:
        t-=1

    ans=True
    while True:
        if t<0:
            break
        max_n,min_n=max(max_n,min_n),min(max_n,min_n)
        if (3**t)//2+1 <= max_n:
            max_n=abs(max_n-3**t)
        else :
            ans=False
            break
        t-=1
    if ans and min_n==0 and max_n==0:
        print(f'#{tc+1} yes')
    else:
        print(f'#{tc+1} no')

 

---

오랜만에 숫자 놀이 하니까 재밌는거 같기도..?

 

SW Expert Academy