백준 21908 - Disk Sort [Python]

https://www.acmicpc.net/problem/21908

21908번: Disk Sort

Ad-Hoc, Constructive, Case Work

 

어떤 종류의 디스크를 빈 막대에 모으기 위해서, 각 디스크마다 6번 이하로 옮겨야 문제의 조건인 6N번 이하로 모든 디스크를 정리할 수 있다.

 

모든 디스크들의 깊이를 위에서부터 1, 2, 3으로 보자.

깊이가 (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 2, 3)일 때, 6번 이하로 옮길 수 있다. 이때, 깊이가 1인 디스크가 항상 존재하므로, 이 경우는 항상 존재하게 된다.

 

그리고, 이러한 방법을 이용하면 마지막에는 한번에 2종류를 정리할 수 있으므로 많아봤자 6(N-1)번이 걸린다.

 

그러면, 마지막에 빈 막대가 N+1번째 막대가 아니어도 3번 더 움직여 마무리할 수 있고, 최대 움직임은 6N - 3이 된다.

 

구현이 죽을맛이다. 화이팅!

깊이가 (1, 1, 2)여도 2가지의 경우가 나오니, 이렇게 다른 경우들도 고려해야 한다

 

그렇게 4000바이트 가량을 열심히 쓰다보면 ac가 나온다. 실수가 없다면

import sys, math
import heapq
 
from collections import deque
 
input = sys.stdin.readline
 
hqp = heapq.heappop
hqs = heapq.heappush
 
 
# input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split().rstrip()))
 
 
# gcd, lcm
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
 
 
def lcm(x, y):
    return x * y // gcd(x, y)
 
 
# prime
def isPrime(x):
    if x <= 1: return False
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True
 
 
# Union Find
# p = [i for i in range(n + 1)]
 
def find(x):
    if x == p[x]:
        return x
    q = find(p[x])
    p[x] = q
    return q
 
 
def union(x, y):
    x = find(x)
    y = find(y)
 
    if x != y:
        p[y] = x
 
 
def getPow(a, x):
    ret = 1
    while x:
        if x & 1:
            ret = (ret * a) % MOD
        a = (a * a) % MOD
        x >>= 1
    return ret
 
 
def getInv(x):
    return getPow(x, MOD - 2)
 
 
############### Main! ###############
 
def swap(A, B):  # Move: From A to B
    ans.append([A[1], B[1]])
    l, r = a[A[0]][A[1]], a[B[0]][B[1]]
    li = 0
    ri = 0
    for i in range(3):
        if d[l][i] == A:
            li = i
        if d[r][i] == B:
            ri = i
    x1, x2, x3, x4 = d[l][li][0], d[l][li][1], d[r][ri][0], d[r][ri][1]
    d[l][li][0], d[l][li][1], d[r][ri][0], d[r][ri][1] = x3, x4, x1, x2
    a[A[0]][A[1]], a[B[0]][B[1]] = a[B[0]][B[1]], a[A[0]][A[1]]
    d[l].sort()
    d[r].sort()
 
ans = []
c = [0 for _ in range(1001)]
 
n = ip()
d = [[[0, 0] for _ in range(3)] for _ in range(n + 1)]
d[0] = [[_ + 1, n + 1] for _ in range(3)]
a = [[0] for _ in range(4)]
for i in range(1, 4):
    b = lmip()
    for j in range(n):
        d[b[j]][c[b[j]]] = [i, j + 1]
        c[b[j]] += 1
    a[i] += b
    a[i] += [0]
 
x = [0, 0]
y = [0, 0]
z = [0, 0]
 
p = n + 1
 
bp = True
for idk in range(n):
    bp = True
    for i in range(n + 1):
        x = [d[i][0][0], d[i][0][1]]
        y = [d[i][1][0], d[i][1][1]]
        z = [d[i][2][0], d[i][2][1]]
 
        if x[1] == y[1] == z[1]:
            continue
        if x[0] + y[0] + z[0] <= 6:
            if x[0] == y[0] == z[0] == 2:
                continue
            bp = False
            break
 
    if bp:
        break
    # print(x, y, z)
    if x[0] == y[0] == z[0] == 1:  # 1
        now = 1
        swap(x, [3, p])
        swap(y, [2, p])
        swap(z, [1, p])
        swap([2, x[1]], y)
        swap([3, x[1]], z)
        p = x[1]
    elif x[0] == y[0] == 1 and 1 < z[0] and z[1] != x[1] and y[1] != z[1]:  # 2
        now = 2
        swap(x, [3, p])
        swap(y, [2, p])
        swap([1, z[1]], x)
        if z[0] == 2:
            swap(z, [1, p])
            swap([3, z[1]], y)
        else:  # z == 3
            swap([2, z[1]], y)
            swap(z, [1, p])
        p = z[1]
    elif x[0] == y[0] == 1:  # 3
        now = 3
        if x[1] == z[1]:
            x[0], y[0] = y[0], x[0]
            x[1], y[1] = y[1], x[1]
        swap(x, [3, p])
        swap(y, [2, p])
        if z[0] == 2:
            swap(z, [1, p])
            swap([3, z[1]], x)
        else:  # z == 3
            swap([2, z[1]], x)
            swap(z, [1, p])
        p = z[1]
    elif x[0] == 1 and y[0] == 2 and x[1] != y[1] and z[1] != x[1] and z[1] != y[1]:  # 4
        now = 4
        swap(x, [3, p])
        swap([1, y[1]], x)
        swap(y, [2, p])
        swap([1, z[1]], y)
        if z[0] == 2:
            swap(z, [1, p])
            swap([3, z[1]], [1, y[1]])
        else:  # z == 3
            swap([2, z[1]], [1, y[1]])
            swap(z, [1, p])
        p = z[1]
    elif x[0] == 1 and y[0] == 2 and z[0] == 3 and x[1] == y[1] and y[1] != z[1]:  # 5
        now = 5
        swap(x, [3, p])
        swap(y, [2, p])
        swap([1, z[1]], y)
        swap([2, z[1]], x)
        swap(z, [1, p])
        p = z[1]
    elif x[0] == 1 and y[0] == z[0] == 2:  # 6
        now = 6
        if x[1] == z[1]:
            y[0], z[0] = z[0], y[0]
            y[1], z[1] = z[1], y[1]
        swap(x, [3, p])
        swap(y, [2, p])
        swap([1, z[1]], y)
        swap(z, [1, p])
        swap([3, z[1]], x)
        p = z[1]
    elif x[0] == 1 and y[0] == 2 and z[0] == 3 and x[1] == z[1]:  # 7
        now = 7
        swap(x, [3, p])
        swap([1, y[1]], x)
        swap(y, [2, p])
        swap(x, y)
        swap([2, x[1]], [1, y[1]])
        swap(z, [1, p])
        p = z[1]
    else:  # 8
        now = 8
        swap(x, [3, p])
        swap([1, y[1]], x)
        swap(y, [2, p])
        swap(z, [1, p])
        p = z[1]
    # print(now)
    # for i in range(1, 4):
    #     print(*a[i][1:])
 
if d[0][0][1] != n + 1:
    swap([1, n + 1], [3, d[0][0][1]])
    swap([2, n + 1], [2, d[0][0][1]])
    swap([3, n + 1], [1, d[0][0][1]])
 
print(len(ans))
for i in ans:
    print(*i)
 
 
 
######## Priest W_NotFoundGD ########

졸면서 적어서 글이 개판인것같다.

수능때문에, 블로그 글을 못썼다. ps도 쉬었고..

그래도 이제 icpc 준비하고 문제도 푸는 겸 글도 다시 열심히 써봐야겠따