우주의 IT 소행성

from collections import deque
n = int(input())
matrix = [(list(map(int, input().split()))) for _ in range(n)]
queue = deque()
queue.append((0, 0))

while queue:
    x, y = queue.popleft()
    jump_size = matrix[x][y]
    dx = [0, jump_size]
    dy = [jump_size, 0]

    for i in range(2):
        nx = dx[i] + x
        ny = dy[i] + y

        if n <= nx or n <= ny:
            continue
        if jump_size == 0:
            continue
        if jump_size == -1:
            print("HaruHaru")
            exit(0)
        queue.append((nx, ny))

print("Hing")

bfs를 통해 이동가능한 모든 경우(우, 하)를 대입시켜 목적지에 도달할 경우

haruharu를, 그렇지 않을 경우 hing을 출력시킨다.

처음에는 주어진 수를 2개의 중복순열로 리스트를 만들어

해당 리스트가 전부 소수로 되어있으면 추출하는 방식으로 했는데, 그 수많은 수들을 매 케이스마다 반복하려니

시간초과가 나왔다.

from itertools import product
import math
for _ in range(int(input())):
    target = int(input())
    array = [True for i in range(target + 1)]
    result = []

    for i in range(2, int(math.sqrt(target)) + 1):
        if array[i]:
            j = 2
            while i * j <= target:
                array[i * j] = False
                j += 1

    data = []
    for i in range(2, target + 1):
        if array[i]:
            data.append(i)

    result = []
    for i in product(data, repeat=2):
        if i[0] + i[1] == target:
            result.append(i)

    if len(result) % 2 == 0:
        index = len(result) // 2 - 1
        print(result[index][0], result[index][1])
    else:
        index = len(result) // 2
        print(result[index][0], result[index][1])

최초 코드

그래서 결국 처음에 에라토스테네스의 체로 구별해 낸 소수 리스트을 1회 이용하여 연산해야 할 방법을 찾아야 했다.

중간값부터 1씩 올리고 / 1씩 내리고 를 반복하며 찾아가는 방식으로 n/2 회로 시간 복잡도를 줄여나갔다.

import math, sys
input = sys.stdin.readline
array = [True for i in range(10001)]

for i in range(2, 101):
    if array[i]:
        j = 2
        while i * j <= 10000:
            array[i * j] = False
            j += 1

for _ in range(int(input())):
    target = int(input())
    x = target // 2
    y = x

    for _ in range(10000):
        if array[x] and array[y]:
            print(x, y)
            break
        x -= 1
        y += 1

결과 코드