[백준] 10158번 개미 ★★

💡문제접근1

• 처음에는 좌우 끝 벽면에 부딪히는 경우, 상하 끝 벽면에 부딪히는 경우 움직인 방향의 반대 방향으로 이동할 수 있도록 bool변수를 선언해주어 각각의 경우를 나누어 코드를 작성했다. 하지만 시간초과가 발생했다. 왜냐하면 이 문제의 마지막에 있는 범위 때문이다.
• w(가로)와 h(세로)는 자연수이며 범위는 2 ≤ w, h ≤ 40,000이고 계산할 시간 t의 범위가 1 ≤ t ≤ 200,000,000이기 때문이다. 선형 탐색으로 위의 과정을 전부 돌리게 된다면 엄청난 시간이 소모된다.

💡코드1

import sys
w, h = map(int, sys.stdin.readline().strip().split())
start_x, start_y = map(int, sys.stdin.readline().strip().split())
t = int(input())

left_right = True   # 오른쪽으로 이동하면 True, 왼쪽으로 이동하면 False
up_down = True      # 위쪽으로 이동하면 True, 아래쪽으로 이동하면 False
cnt = 0
while True:
    if cnt == t:
        print(start_x, start_y)
        break
    else:
        # 가로축의 경우
        if start_x == 0:
            left_right = True
            start_x += 1
        elif start_x == w:
            left_right = False
            start_x -= 1
        else:
            if left_right:
                start_x += 1
            else:
                start_x -= 1

        # 세로축의 경우
        if start_y == 0:
            up_down = True
            start_y += 1
        elif start_y == h:
            up_down = False
            start_y -= 1
        else:
            if up_down:
                start_y += 1
            else:
                start_y -= 1

        cnt += 1

💡문제접근2

이 문제의 주요 알고리즘이 애드 혹인 이유가 여기 있는 것 같다고 생각해서 종이에 적어가면서 한참을 고민하다가 규칙을 발견하고 그것을 코드로 작성했다.

💡코드2(메모리 : 30748KB, 시간 : 40ms)

import sys
w, h = map(int, sys.stdin.readline().strip().split())
start_x, start_y = map(int, sys.stdin.readline().strip().split())
t = int(input())

a = (start_x + t) // w	# 개미가 시작 지점에서 t초만큼 움직인 값을 w로 나눠준다면 왕복 횟수가 나온다.
b = (start_y + t) // h	# 개미가 시작 지점에서 t초만큼 움직인 값을 h로 나눠준다면 왕복 횟수가 나온다.


if a % 2 == 0:
    start_x = (start_x + t) % w
else:
    start_x = w - (start_x + t) % w

if b % 2 == 0:
    start_y = (start_y + t) % h
else:
    start_y = h - (start_y + t) % h

print(start_x, start_y)

💡소요시간 : 1h