[python] 백준 10158 - 개미

출처 : 백준,  https://www.acmicpc.net/problem/10158

10158번: 개미

 

 

첫 번째 풀이 : 시간초과

 

if __name__ == '__main__':
  w, h = map(int, input().split())
  position = list(map(int, input().split()))
  target = int(input())

  dx = 1
  dy = 1
  time = 0

  while True:
    if time == target:
      break

    if position[0] == w or position[0] == 0:
      dx *= -1

    if position[1] == 0 or position[1] == h:
      dy *= -1

    position[0] += dx
    position[1] += dy

    time += 1

  print(position)

 

그냥 1칸씩 이동하면서 계산하는 풀이다.

사실 1 ≤ t ≤ 200,000,000라는걸 보자마자 아 시간초과 걸릴 것 같은데라고 생각은 했지만....

혹시나해서 해봤는데 안됐다.

 

 

두 번째 풀이 : 실패

 

if __name__ == '__main__':
  w, h = map(int, input().split())
  x, y = map(int, input().split())
  time = int(input())

  x = x + time % (2 * w)
  y = y + time % (2 * h)

  if x >= w:
    x = w - (x - w)

  if y >= h:
    y = h - (y - h)

  print(x, y)

 

반례

 

3 3
1 2
5

#기대 출력 : 0 1
#실제 출력 : 0 -1

 

아이디어는 2차원 배열에서 대각선으로 움직이는 것으로 생각하는게 아니라
가로, 세로 각각으로 1차원으로 왔다갔다하는 것으로 생각하는 것이다.

 

 

t	0	1	2	3	4	5	6	7	8
x	2	3	2	1	0	1	2	3	2

 

보면 시간 t에 따라 x좌표가 0, 1, 2, 3, 2, 1, 0과 같은 패턴으로 주기적으로 제자리로 다시 돌아오는 것을 알 수 있다.

바라보는 방향까지 같은 동일한 위치로 돌아오기까지를 하나의 순환으로 본다면

 

t	0	1	2	3	4	5	6	7	8
x	2	3	4	5	0	1	2	3	4

 

와 같이 추론할 수 있고, 한 변을 왕복하는 것이기 때문에

각 변의 길이 * 2한 값과 나머지 연산으로 무언가 패턴을 끌어낼 수 있겠다는 추론을 할 수 있다.

 

그래서 시간을 각 변의 2배한 값으로 나머지 연산한 값을 현재 위치에 더해주고,

이 것이 각 가로나 세로보다 크다면(위 예제에서 3보다 크다면) 4, 5 부분이므로 따로 연산하여 위치를 구해주는 코드를 짰다.

 

근데 틀림.

 

 

세 번째 풀이

 

if __name__ == '__main__':
  w, h = map(int, input().split())
  x, y = map(int, input().split())
  time = int(input())

  x = x + time % (2 * w)
  y = y + time % (2 * h)

  if x > 2 * w:
    x = x % (2 * w)

  if y > 2 * h:
    y = y % (2 * h)

  if x > w:
    x = 2*w - x

  if y > h:
    y = 2*h - y

  print(x, y)

 

위 코드에서 로직은 바뀐 건 없으나 시간을 나눈 값, 즉 이동 횟수가 각 변의 2배가 되는 경우만 고려해서

현재 위치에서 시간을 나눈 값을 더한 값이 각 변의 2배를 초과하는 경우를 고려해주지 못했다.

이 경우에 대한 처리를 따로 추가하여 완료.

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

로직을 찾는건 쉬웠는데 2번째 풀이와 같이 생각지도 못한 부분에서 에러가 나는 경우에

반례를 찾는 것이 너무 어려웠고 결국 반례는 질문하기를 참고했다.