생각해서 브루트포스 탐색 범위를 줄여야하는 경우1 (장난감 강아지)

1. 문제

 

31287번: 장난감 강아지 (acmicpc.net)

31287번: 장난감 강아지

 

 

2. 풀이

 

의외로 생각을 요구해서 배울 점이 있는 문제

 

위,아래,왼쪽,오른쪽으로 강아지가 움직이는데.. 문제는 길이 2000인 문자열 S를 최대 $10^{9}$번 반복시켜서 

 

2000*1000000000번 강아지가 움직일 수 있다

 

이때 원점에서 움직이는데 다시 원점으로 돌아올 수 있는지 확인해야하는 문제

 

2000*1000000000번을 1초안에 다 해볼수는 없을 것

 

근데 길이가 N인 문자열 S만큼 강아지를 1번 움직여본다면... 강아지가 원점에서 얼마만큼 벗어날 수 있을까?

 

운 좋으면 다시 원점으로 돌아올거고, 최악의 경우에는 길이 N만큼 원점에서 벗어나게 된다.

 

따라서 원점에서 길이 N+1이상으로 벗어나면 몇번을 해도 다시는 돌아올 수 없다

 

또한 원점에서 벗어난다고 했을때, 길이 N인 문자열 S를 움직인다면 최소한 길이 1만큼 벗어날 수 있다.

 

따라서 길이 N인 문자열 S만큼 움직이는 행위를 했을때 원점에서 길이 0~N까지 벗어날 수 있다.

 

만약 항상 최소 길이 1만큼 벗어난다고 했을때, N인 문자열 S만큼 N번 움직이면 길이 N만큼 벗어날 수 있다.

 

그러므로 길이 N인 문자열 S만큼 움직이는 행위를 했을때, 무조건 이 행위 N번 안에 돌아오냐 돌아오지 않냐를 결정할 수 있다.

 

그래서 길이 N인 문자열 S만큼 움직이는 행위를 N번 모두 해봐서 좌표 움직임을 브루트포스로 찾아보면서

 

원점에 돌아오는 경우가 있는지 검사하면 $O(N^{2})$으로 문제를 해결할 수 있다

 

당연하지만 문자열 S를 K번 붙이는 것이기 때문에 N보다 K가 더 작다면, S를 N번 도는게 아니라 K번 돌아야함 

 

n,k = map(int,input().split())

s = input()

delta = {'U':[0,1],'R':[1,0],'D':[0,-1],'L':[-1,0]}

x = 0
y = 0

find = False

for _ in range(min(n,k)):
    
    for i in range(n):
        
        x += delta[s[i]][0]
        y += delta[s[i]][1]
        
        if x == 0 and y == 0:
            
            find = True
            
            break
    
    if find:
        
        break

if find:
    
    print('YES')
    
else:
    
    print('NO')