사용자 도구

사이트 도구


ps:problems:boj:31287

장난감 강아지

ps
링크acmicpc.net/…
출처BOJ
문제 번호31287
문제명장난감 강아지
레벨실버 2
분류

시뮬레이션

시간복잡도O(n)
인풋사이즈n<=2000
사용한 언어Python 3.11
제출기록31120KB / 40ms
최고기록40ms
해결날짜2024/02/15

풀이

  • 보통 이런 문제를 푸는 요령은 적당한 횟수만큼만 시뮬레이션을 돌려보고, 그때까지 조건을 만족하는 경우가 없다면, 영원히 조건을 만족하는 경우가 없다고 판단하는 것 이다.
  • 이 문제에서의 그 적당한 횟수는 얼마일까. 문자열 S를 한번 실행했을때, 원점으로 돌아오는 경우가 생긴다면 자명하고, 그렇지 않다면 S의 종료시점에 원점으로부터 X만큼 떨어져 있게 될것이다. S를 M번 반복 실행하고나면, 원점과의 거리는 X*M이 될것이다. 한번 S를 수행하는 동안 이동할수 있는 거리는 N이므로, 원점과의 거리가 N보다 커지는 시점이 되면, 이후에는 원점으로 돌아오는 경우가 생기지 않는다.
  • 이 논리를 따라서, 이동 한번씩 시뮬레이션을 돌리다가 원점과의 거리가 N보다 커지면 종료하는 식으로 구현할수 있다.
  • 하지만, S를 하나의 수행 단위로 시뮬레이션하면 더욱 효율적으로 구현할수 있다. S를 수행하면서 지나가는 위치들과 S를 마친 후에 이동되는 위치를 계산해두면, 현재 위치에서 한번 S를 실행할때 원점을 거치는지와 다음 위치가 어디로 가는지를 한번에 계산할수 있다.
  • 앞에서의 논리에 따라서, S를 실행해봐야 하는 최대 횟수는, S를 한번 실행한 뒤의 원점과의 거리가 X일때 N/X번이다. 하지만 더 구현을 간단히 하려면 그냥 S를 N번 돌리는 식으로 처리하더라도 시간복잡도상 충분히 가능하다
  • 이렇게 구현할때의 시간복잡도는, 먼저 S를 한번 돌리면서 방문하는 위치들을 확인하는데에 O(n), 이후에 S단위로 이동하는 것을 min(n,K)번 수행하므로, 총 O(n + min(n,K)) = O(n) 이 된다.

코드

"""Solution code for "BOJ 31287. 장난감 강아지".

- Problem link: https://www.acmicpc.net/problem/31287
- Solution link: http://www.teferi.net/ps/problems/boj/31287

Tags: [simulation]
"""

DX = {'U': 0, 'D': 0, 'L': -1, 'R': 1}
DY = {'U': 1, 'D': -1, 'L': 0, 'R': 0}


def main():
    N, K = [int(x) for x in input().split()]
    S = input()

    x = y = 0
    visited_pos = {(x := x + DX[c], y := y + DY[c]) for c in S}
    if any((-x * i, -y * i) in visited_pos for i in range(min(N, K))):
        print('YES')
    else:
        print('NO')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
E J᠎ H Q T
 
ps/problems/boj/31287.txt · 마지막으로 수정됨: 2024/02/15 03:23 저자 teferi