초이의 끄적끄적

# 17406 배열 돌리기 4 (골드4)

• 다시 풀어보기
• Point. DFS, 방향벡터, 백트레킹 기법 사용

from copy import deepcopy

N, M, K = map(int, input().split()) # 배열 A크기 N,M, 회전 연산 개수 K
A = [list(map(int,input().split())) for _ in range(N)] # 배열 A 수
Q = [tuple(map(int, input().split())) for _ in range(K)] # 회전 연산 정보
dx,dy = [1,0,-1,0],[0,-1,0,1]   # 방향벡터 남서북동
ans = 10000 # 배열 A의 값의 최솟값

def value(arr): # 행의 최소값
    return min([sum(i) for i in arr])

def convert(arr, qry): # 회전
    (r, c, s) = qry # 중심점 (r,c) 거리 s
    r, c = r-1, c-1 # 좌표가 0,0 시작이기 때문에 -1 해줌
    new_arr = deepcopy(arr)
    for i in range(1, s+1):
        rr, cc = r-i, c+i
        for w in range(4): # 방향 4번 바꿈
            for d in range(i*2): #
                rrr, ccc = rr + dx[w], cc+dy[w]
                new_arr[rrr][ccc] = arr[rr][cc]
                rr, cc = rrr, ccc
    return new_arr

def dfs(arr, qry):
    global ans # 전역변수 설정
    if sum(qry) == K: # 쿼리를 다 처리했을 경우
        ans = min(ans, value(arr)) # 최소값 저장
        return
    for i in range(K):
        if qry[i]:
            continue
        new_arr = convert(arr, Q[i]) # 쿼리 회전
        qry[i] = 1  # 백트래킹 기법
        dfs(new_arr, qry)
        qry[i] = 0

dfs(A,[0 for i in range(K)])
print(ans)

단계별풀기 - 브루트 포스

# 1018 체스판 다시 칠하기(실버5) (참고)

• 크기가 n*m이고, 흰색과 검은색으로 막 칠해져 있는 보드판이 있다.
• 이 보드판을 잘라서 8*8크기의 체스판을 만들려고 한다.
• 체스판은 흰색과 검은색이 번갈아가며 체크무늬를 이루어야한다.
• 보드판을 잘라서, 체스판을 만들기 위해서 알맞게 색을 고쳐서 체크무늬를 만들어야 한다.
• 고쳐야 하는 색의 최소값을 구하라
• Point. 인덱스 합이 짝수인지 홀수인지로 체크무늬를 판단할 수 있다.

n, m = map(int, input().split())
board = list()
mini = list()

for _ in range(n):
    board.append(input())

for a in range(n - 7): # 8*8로 자르기
    for i in range(m - 7):
        idx1 = 0
        idx2 = 0
        for b in range(a, a + 8):
            for j in range(i, i + 8):              # 8X8 범위를 B와 W로 번갈아가면서 검사
                if (j + b)%2 == 0:
                    if board[b][j] != 'W': idx1 += 1
                    if board[b][j] != 'B': idx2 += 1
                else :
                    if board[b][j] != 'B': idx1 += 1
                    if board[b][j] != 'W': idx2 += 1
        mini.append(idx1)                          # W로 시작했을 때 칠해야 할 부분
        mini.append(idx2)                          # B로 시작했을 때 칠해야 할 부분

print(min(mini))

ex) n = 10, m = 13일 경우 len(mini) = (10-7)*(13-7)*2 = 36개 그 값들 중 가장 작은 수 출력

# 1932 정수 삼각형 (실버1)

• 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
• Point. 모든 경로를 따지면 2^50 -> 이번생에 못푼다
• DP문제 (다음 상태를 저장하고 사용함)
  1. 상태를 정의한다 
  2. 점화식을 찾는다(구한다) 
  3. 시간복잡도를 계산한다
  4. 코딩한다(재귀 or 반복문 사용)

N = int(input())
# DP[i][j] : i,j 도착했을 때 최대값
# DP[i][j] = max(DP[i-1], DP[i-1][j]) + A[i][j]
A = [[0 for _ in range(N+1)] for i in range(N+1)]
DP = [[0 for _ in range(N+1)] for i in range(N+1)]

for i in range(1, N+1):
    tmp = list(map(int, input().split()))
    for j in range(1, i+1):
        A[i][j] = tmp[j-1]

for i in range(1, N+1):
    for j in range(1, i+1):
        DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + A[i][j]

print(max(DP[-1]))

단계별풀기 - 브루트 포스

# 7568 덩치 (실버5)

• 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다.
• 여러분은 입력에 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백문자로 분리되어야 한다.
• point. 정렬 ㄴㄴ, 그냥 자기보다 크고 무거운(둘 다 큰) 사람이 몇 명인지 쟤서 자기 등수만 정하면 된다.

tc = int(input())
student_list = []

for _ in range(tc):
    x, y = map(int, input().split())
    student_list.append((x, y))

for i in student_list:
    rank = 1
    for j in student_list:
        if i[0] < j[0] and i[1] < j[1]:
                rank += 1
    print(rank, end = " ")

# 12100 2048(Easy) (골드2)

• 어렵... 또 풀어보자...ㅠ
• 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
• 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
• 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

from copy import deepcopy

N = int(input())
Board = [list(map(int, input().split())) for i in range(N)] # n*n 보드 입력받기

def rotate90(B, N): #판 90도 회전시키기(암기할것)
    NB = deepcopy(B) # 배열 복사하기 NB = B 하면 주소값만 복사됨
    for i in range(N):
        for j in range(N):
            NB[j][N-i-1] = B[i][j] # 90도 돌리기
    return NB

def convert(lst, N): # 슬라이드 했을 때 결과물
    new_list = [i for i in lst if i]
    for i in range(1, len(new_list)):
        if new_list[i-1] == new_list[i]: #같은수이면
            new_list[i-1] *= 2 # 합치고
            new_list[i] = 0 # 나머지 제거
    new_list = [i for i in new_list if i]
    return new_list + [0] * (N-len(new_list))

def dfs(N, B, count):
    ret = max([max(i) for i in B]) #보드의 최대값
    if count == 0: # 5번 다 돌았을 때 최대값 출력
        return ret
    for _ in range(4): # 상하좌우 이동 경우의 수
        X = [convert(i, N) for i in B] # 슬라이드
        if X != B:
            ret = max(ret, dfs(N, X, count-1))
        B = rotate90(B, N) # 회전
    return  ret

print(dfs(N, Board, 5))

# 16768 Mooyo Mooyo (골드4)

• 셀 높이 (1≤N≤100) 및 10 셀 너비
• 각 셀은 비어 있거나 (0으로 표시) 9 가지 색상 중 하나 (문자 1..9로 표시)의 건초입니다. 중력으로 인해 건초 더미가 아래로 떨어 지므로 건초 더미 아래에 0 셀이 없습니다.
• 두 셀이 가로 또는 세로로 직접 인접하고 0이 아닌 동일한 색상을 갖는 경우 동일한 연결된 영역에 속합니다. 최소한으로 연결된 지역이 존재할 때에 K세포, 건초 더미가 모두 사라지고 0으로 변합니다. 이러한 연결된 영역이 동시에 여러 개 있으면 모두 동시에 사라집니다. 그 후 중력으로 인해 건초 더미가 아래로 떨어져 0이 된 결과 K세포 중 일부를 채울 수 있습니다. 결과 구성에서 다시 적어도 크기의 연결된 영역이있을 수 있습니다. K세포. 만약 그렇다면, 그것들도 사라지고 (동시에, 그러한 영역이 여러 개인 경우), 중력은 나머지 세포를 아래쪽으로 당기고, 적어도 크기의 연결된 영역이 없을 때까지 프로세스가 반복됩니다. K에 있다.
• Mooyo Mooyo 보드의 상태를 감안할 때 이러한 작업이 발생한 후 보드의 최종 사진을 출력하십시오.
• point. 함수 나눠서 풀기 / Flood Fill /  dfs사용하기 / 갯수세기, 지우기, 내리기로 나눠서 코드 작성
• 반복해서 풀어보기

def new_array(N):
    return [[False for i in range(10)] for _ in range(N)]

N, K = map(int, input().split())
M = [list(input()) for _ in range(N)]
ck = new_array(N)
ck2 = new_array(N)
dx, dy = [0,1,0,-1], [1,0,-1,0] #방향벡터 설정

def dfs(x,y): # 갯수세기
    ck[x][y] = True # 그룹에 포함되어 있는가
    ret = 1
    for i in range(4): # 4방향 검사
        xx,yy = x+dx[i], y+dy[i]
        if xx<0 or xx>=N or yy<0 or yy>=10: # 구간 내에 있는지 확인
            continue
        if ck[xx][yy] or M[x][y] != M[xx][yy]: # 체크가 되어 있거나 연결이 안되거나
            continue
        ret += dfs(xx,yy)
    return ret

def dfs2(x,y, val): # 지우기
    ck2[x][y] = True # 지워도 되는가
    M[x][y] = '0' # 0으로 바꿔줌
    for i in range(4):
        xx, yy = x + dx[i], y + dy[i]
        if xx < 0 or xx >= N or yy < 0 or yy >= 10:  # 구간 내에 있는지 확인
            continue
        if ck2[xx][yy] or M[xx][yy] != val:
            continue
        dfs2(xx,yy,val)

def down(): #내리기
    for i in range(10): # 세로줄부터 확인하기
        tmp = []
        for j in range(N):
            if M[j][i] != '0': #0이 아닌 수들 저장
                tmp.append(M[j][i])
        for j in range(N-len(tmp)): #0이 아닌 수의 갯수 빼고 0 채우고
            M[j][i] = '0'
        for j in range(N-len(tmp),N): #나머지 수 채워넣기
            M[j][i] = tmp[j- (N -len(tmp))]

while True:
    exist = False
    ck = new_array(N)
    ck2 = new_array(N)
    for i in range(N):
        for j in range(10):
            if M[i][j] == '0' or ck[i][j]: # 0이거나 이미 체크했으면 넘어가기
                continue
            res = dfs(i,j) # 개수 세기
            if res >= K:    # 개수가 K보다 같거나 크면
                dfs2(i,j, M[i][j]) # 지우기
                exist = True
    if not exist:
        break
    down() # 내리기

for i in M:
    print(''.join(i))

단계별풀기 - 브루트 포스

# 2798 블랙잭 (브론즈2)

• N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

n,m = map(int, input().split())
n_list = list(map(int, input().split()))
sum_list = []
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            nsum = n_list[i] + n_list[j] + n_list[k]
            if nsum <= m:
                sum_list.append(nsum)

print(max(sum_list))

# 2231 분해합 (브론즈2)

• 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
• 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.
• 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.
• point. 숫자 각자리 더하기 list(map(int, str())) 사용

1) 틀린 답 -> 생성자가 없는 경우 0을 출력해야함을 간과함

n = int(input())
for i in range(1,n+1):
    div_num = list(map(int, str(i)))
    sum_num = i +sum(div_num)
    if sum_num == n:
        print(i)
        break

2) 정답

N = int(input())
print_num = 0
for i in range(1, N+1):
    div_num = list(map(int, str(i)))
    sum_num = i + sum(div_num)
    if(sum_num == N):
        print_num = i
        break
print(print_num)

# 1080 행렬 (실버 2)

• 0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.
• 행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0)
• 첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.
• point. A,B 행렬값을 비교해서 다르면 3*3 크기만큼 flip 시켜준다

N, M = map(int, input().split())
A = [list(map(int, list(input()))) for _ in range(N)]
B = [list(map(int, list(input()))) for _ in range(N)]

def flip(x,y,A):
    for i in range(3):
        for j in range(3):
            A[x+i][y+j] ^= 1 # xor

ans = 0
for i in range(N-2):
    for j in range(M-2):
        if A[i][j] != B[i][j]:
            flip(i,j,A)
            ans +=1

if A != B:
    print(-1)
else:
    print(ans)

# 2014 소수의 곱 (골드2)

• K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자. 단 정답은 2**31보다 작은 자연수이다.
• point. 그리디 알고리즘 젤 어려운 문제, 네이버같은 곳에서 나옴
• heap 우선순위 큐를 사용하여 큐 안에 있는 값들 중 최소 값을 반환한다. (힙큐 최소힙 기반)
• 중복 처리 중요

import heapq
import copy

K,N = map(int, input().split())
p_list = list(map(int, input().split()))

lst, ck = copy.deepcopy(p_list), set() # ck 중복된 수를 포함하지 않기 위해

heapq.heapify(lst)
ith = 0

while ith < N :
    mn = heapq.heappop(lst) # 꼭대기값
    if mn in ck:
        continue
    ith += 1
    ck.add(mn)
    for i in p_list:
        if mn*i < 2**32:
            heapq.heappush(lst, mn*i)
print(mn)

단계별풀기 - 재귀

# 2447 별 찍기 -10(실버1)

• 설명..

def star(i):
    global arr
    idx = [ i for i in range(n) if (i//3**cnt_)%3 ==1]
    for i in idx:
        for j in idx:
            arr[i][j] = " "

n = int(input())
v = n
cnt = 0
while v != 1:
    v/=3
    cnt +=1
arr = [["*"]*n for _ in range(n)]
for cnt_ in range(cnt):
    star(cnt_)

print('\n'.join([''.join([str(i) for i in row]) for row in arr]))

# 11729 하노이 탑 이동 순서 (실버2)

• 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
  1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
  2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
• 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
• point. 하노이탑 이동 규칙. n개의 원판이 있을 때, n-1개의 원판 즉, 맨 밑의 원판을 제외하고 나머지 원판들을 1번에서 2번으로 옮긴 뒤, 맨 밑의 원판을 1번에서 3번으로 옮긴다. 그리고 n-1개의 원판들을 다시 2번에서 3번으로 옮긴다.

def hanoi(disk, start, mid, end):
    if disk == 1:
        print(start, end)
    else:
        hanoi(disk - 1, start, end, mid) # 목적지가 아닌 곳으로 재귀적으로 이동
        print(start, end)
        hanoi(disk - 1, mid, start, end) # 다른 곳으로 옮겼던 원반들을 그 위에 얹는다

total_disk = int(input())
total_mvmt = 0

for disk in range(total_disk):
    total_mvmt = total_mvmt * 2
    total_mvmt += 1

print(total_mvmt)
hanoi(total_disk, 1, 2, 3)

# 16676 근우의 다이어리 꾸미기 (브론즈2)

• point. 그리디 알고리즘 -> 규칙성을 찾아라
• 0~10 => 1 / 11~110 => 2 / 111~1110 => 3 / 1111~11110 =>4 ~~
• ex) n = 88
• 입력받는 정수의 길이를 1로 표시
• n이 일의 자리 정수라면 1 
• n이 11보다 크거나 같다면 두 개의 스티커팩으로 표현 가능
• n이 11보다 작다면(10인 경우) 한 개의 스티커팩으로 표현 가능 

N= input()
S = '1'*len(N)

if len(N) == 1:
    print(1)
elif int(N) >= int(S):
    print(len(N))
else:
    print(len(N)-1)

# 2437 저울 (골드3)

• 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.
• 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 
• point. 그리디 알고리즘 -> 규칙성을 찾아라
• 현재까지의 합 + 1 보다 큰 값이 다음 인덱스에 저장된 수라면 이전의 추들로 무게를 구할 수 없다.

n, a = int(input()), sorted(list(map(int, input().split())))
ans = 0
for i in a:
    if i <= ans +1:
        ans += i
    else:
        break
print(ans+1)

단계별풀기 - 기본수학2

# 1002 터렛 (실버4)

• 조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.
• 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.
• point. 원과 원의 접점의 개수를 구하는 문제
  
  1. 두 원이 일치하는 경우 -> -1, 0
  2. 두 원이 한 점에서 만나는 경우(외접, 내접) -> 1
  3. 두 원이 만나지 않는 경우 -> 0
  4. 두 원이 두 점에서 만나는 경우 -> 2

t = int(input())
for i in range(t):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())
    d = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
    rs = r1 + r2
    rm = abs(r1 - r2)
    if d == 0:
        if r1 == r2:
            print(-1)
        else:
            print(0)
    else:
        if d == rs or d == rm:
            print(1)
        elif d < rs and d > rm:
            print(2)
        else:
            print(0)

단계별풀기 - 재귀

# 10872 팩토리얼 (브론즈 3)

• 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

def fac(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    return  n * fac(n-1)

N = int(input())
print(fac(N))

# 10870 피보나치수 5 (브론즈2)

• 첫째 줄에 n번째 피보나치 수를 출력한다.

def f(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return  f(n-1) + f(n-2)

N = int(input())
print(f(N))

# 1439 뒤집기 (실버5)

• 0과 1로만 이루어진 문자열에서 연속구간 뒤집기를 통해 한문자로만 이루어진 문자열을 만들려 할때, 뒤집기 시행횟수 구하기
• point. 그리디 알고리즘 -> 규칙성을 찾아라
• 뒤에 문자랑 비교해서 같은 문자끼리 뭉텅이 구하기 -> 뭉텅이//2

s = input()
count = 0
for i in range(len(s)-1):
    if s[i] != s[i+1]:
        count +=1
print((count+1)//2)

단계별풀기 - 기본수학2

# 1085 직사각형에서 탈출 (브론즈3)

• 한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오.
• point. (0.0)에 가까운 x,y 거리도 고려해야한다.

x, y, w, h = map(int, input().split())
print(min(w-x, h-y, x, y))

# 3009 네 번째 점 (브론즈3)

• 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오.

x_list = []
y_list = []
for i in range(3):
    x, y = list(map(int, input().split()))
    x_list.append(x)
    y_list.append(y)

for i in range(3):
    if x_list.count(x_list[i]) == 1:
        x = x_list[i]
    if y_list.count(y_list[i]) == 1:
        y = y_list[i]
print(x,y)

# 4153 직각삼각형 (브론즈3)

• 주어진 세변의 길이로 삼각형이 직각인지 아닌지 구분하시오.
• 각 입력에 대해 직각 삼각형이 맞다면 "right", 아니라면 "wrong"을 출력한다.

while True:
    rec_list = list(map(int, input().split()))
    if rec_list[0] == 0 & rec_list[1] == 0 & rec_list[2] == 0:
        break
    rec_max = max(rec_list)
    rec_list.remove(rec_max)

    if rec_max**2 == rec_list[0]**2 + rec_list[1]**2:
        print("right")
    else:
        print("wrong")

# 3053 택시 기하학 (브론즈3)

• 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다.
• 유클리드 기하학 원의 넓이 : 반지름 * 반지름 * 3.1415...(파이)
• 택시 기하학에서의 반지름이 R인 원의 넓이란, “두 대각선의 길이가 2R인 마름모의 넓이” 와 같다

import math
r = int(input())
print(r*r*math.pi)
print(r*r*2)

단계별풀기 - 기본수학2

# 9020 골드바흐의 추측 (실버1)

• 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.
• 각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.
• 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.
• point. 시간초과 에라토스테네스의 체 사용해서 소수 구하기 
  • prime 값이 True면 소수
• point. 두 소수의 차이가 가장 작은것을 출력한다 & 작은 소수부터 출력한다 -> 중간값부터 확인해본다
  • n = 8 이면 4,4 -> 3,5(break) -> 2,6 -> 1,7 순으로 확인
  • n = 10 이면 5,5(break) -> 4,6 -> 3,7 -> 2,8 -> 1,9 순으로 확인한다. 
  • n = 16  이면 8,8, -> 7,9 -> 6,10 -> 5,11(break) -> ...

def isprime(n):
    n += 1
    prime = [True] * n  # n개의 [True]가 있는 리스트 생성
    for i in range(2, int(n ** 0.5) + 1):  # n의 제곱근까지만 검사
        if prime[i]:  # prime[i]가 True일때
            for j in range(2 * i, n, i):  # prime 내 i의 배수들을 False로 변환
                prime[j] = False
    return prime

for _ in range(int(input())):
    n = int(input())
    prime_list = isprime(n)
    half = n//2
    for i in range(half, 1, -1):
        if prime_list[i] and prime_list[n-i]:
            print(i, n-i)
            break