백준 # 31287번 장난감 강아지 - 파이썬

4 2 URLD

YES

3 2 URD

NO

시뮬레이션으로는 풀리지 않고 시간 초과가 난다.
생긴 도형의 최종점과 원점의 관계를 통해 그림을 새로 그리지 않고 원점을 최종점(x,y)에 대해 -x, -y 만큼 이동한다고 생각하고 문제를 풀었지만 시간 초과를 도무지 해결할 수가 없었다.
먼저 1회 순회하면서 0,0을 지나는지, 어느 점을 지나는지 기록하고, 최종점을 구한 뒤에 2회 반복부터는 좌표에 대한 함수로 구하려고 했는데.... 안되었다.

 
망한 코드를 보자. 이거보다 개선된 k회 포지션을 기준으로 하는 코드가 있는데 의미없다.

def can_return_to_origin(n, k, text):
    x, y = 0, 0
    positions = set() # 거쳐간 좌표들을 저장할 집합
    # 명령어 순회
    for t in text[:-1]:
        if t == 'U':
            y += 1
        elif t == 'D':
            y -= 1
        elif t == 'L':
            x -= 1
        elif t == 'R':
            x += 1
        positions.add((x, y))

    # k번 이내에 원점으로 돌아올 수 있는지 확인
    for repeat in range(k):
        # 반복마다 원점을 도형이 이동하는 반대 방향으로 옮기며
        # 이동 경로에 걸리는 점이 있는지 확인
        final_position = (repeat * -x, repeat * -y)
        if final_position in positions:
            return "YES"
    return "NO"
import sys
inp = sys.stdin.readlines()
n, k = map(int, inp[0].split())  # n: 명령어의 길이, k: 반복 횟수

# 결과 출력
print(can_return_to_origin(n, k, inp[1]))

 
 
혹시나 하고 먼저 최종 좌표를 찾고 따라그리면서 원점과 만나는 점이 있는지 점검하면 되는지 해 봤는데... 된다..
왜 두 번 세는 것이 한번 세는 것보다 빠른가...
collections.Counter 꼭 쓰세요 ㅠㅠ 짱빨라요.
점 기록과 탐색이 시간을 어마어마하게 잡아먹은 것이었다.....
 

from collections import Counter
import sys


def return_to_origin(n, k, text, destination):
    fx, fy = destination
    dist = abs(fx) + abs(fy)
    if dist == 0:
        return "YES"
    x, y = 0, 0
    for t in text[:-1]: # 명령어 순회
        if t == 'U': y += 1
        elif t == 'D': y -= 1
        elif t == 'L': x -= 1
        elif t == 'R': x += 1
        dist_new = abs(x) + abs(y)
        if fx*y == fy*x and dist_new//dist < k and dist_new%dist == 0:
            return "YES"
    return "NO"

inp = sys.stdin.readlines()
n, k = map(int, inp[0].split())  # n: 명령어의 길이, k: 반복 횟수
text = inp[1][:-1]
counter = Counter(text)
ud = counter['U'] - counter['D']
lr = counter['R'] - counter['L']
destination = (lr, ud)

print(return_to_origin(n, k, text, destination))