import sys
input = sys.stdin.readline
dy = [1,0,-1,0]
dx = [0,1,0,-1]
def roll():
global fishbowl
h = len(fishbowl)
if h==1:
w = 1
else:
w = len(fishbowl[-1])
if len(fishbowl[0])-w < h:
return False
newfishbowl = [[0]*h for i in range(w+1)]
newfishbowl[0] = fishbowl[0][w:]
for y in range(h):
for x in range(w):
newfishbowl[w-x][y] = fishbowl[y][x]
fishbowl = newfishbowl
return True
def distribute():
List = []
for y in range(len(fishbowl)):
for x in range(len(fishbowl[y])):
for i in range(2):
y1,x1 = y+dy[i],x+dx[i]
try:
diff = fishbowl[y][x]-fishbowl[y1][x1]
except:
continue
if diff >= 5:
diff //= 5
elif diff <= -5:
diff = -(abs(diff)//5)
else:
continue
List.append((y,x,diff))
List.append((y1,x1,-diff))
for y,x,diff in List:
fishbowl[y][x] -= diff
def organize():
global fishbowl
newfishbowl = []
for x in range(len(fishbowl[0])):
for y in range(len(fishbowl)):
try:
newfishbowl.append(fishbowl[y][x])
except:
continue
fishbowl = [newfishbowl]
def fold():
global fishbowl
newfishbowl = []
newfishbowl.append(fishbowl[0][N//2:])
newfishbowl.append([*reversed(fishbowl[0][:N//2])])
fishbowl = newfishbowl
newfishbowl = []
newfishbowl.append(fishbowl[0][N//4:])
newfishbowl.append(fishbowl[1][N//4:])
newfishbowl.append([*reversed(fishbowl[1][:N//4])])
newfishbowl.append([*reversed(fishbowl[0][:N//4])])
fishbowl = newfishbowl
N,K = map(int,input().split())
fishbowl = [[*map(int,input().split())]]
cnt = 0
while True:
finish = True
Min = min(fishbowl[0]) #1번과정
for i in range(N):
if fishbowl[0][i] == Min:
fishbowl[0][i] += 1
else:
if fishbowl[0][i]-Min > K:
finish = False
if finish:
break
while roll(): #2번과정
continue
distribute() #3번과정
organize() #4번과정
fold() #5번과정
distribute() #6번과정
organize() #7번과정
cnt += 1
print(cnt)
구현량이 어마어마한 문제이다.
코드에서도 볼 수 있듯이 문제에서 요구하는 처리과정만 7개가 된다.
하지만 각 과정을 하나하나 떼어놓고 보면 어려울만한건 한개도 없고, 테스트케이스가 친절하게 나와있기 때문에 시간이 소요될 뿐 매우 쉽게 풀 수 있다.
단순 노가다 구현인데 플래티넘이라는 점에서 큐빙 [백준 5373번] 큐빙 (Python3) (tistory.com) 과 비슷하다.
알고리즘은 어려울게 하나도 없기 때문에 따로 설명할 만한건 없고, 풀면서 알게된 팁을 몇 가지 말하자면,
1. 처음부터 어항을 이중리스트로 만드는 것이 좋다. len(fishbowl)로 높이를 알아야하므로
2. 어항의 각 층이 너비가 다르기 때문에 인덱스 예외처리를 굳이 하나하나 조건을 나누기보다는 try,except라는 무적함수를 사용해주면 쉽게 풀 수 있다.
3. 이때 2번에서 주의해야할 점은 인덱스가 음수값이어도 try함수가 오류가 안나기 때문에 (-1인덱스가 가능하므로) + 방향으로만 탐사하는것이 좋다.
4. 3번 과정과 6번 과정에서 차이를 5로 나눈 몫을 구할 때 차이값이 음수인지 양수인지를 구분해주어야한다. (음수를 나누면 몫이 1 작아질 수 있다)
5. 구현해야할 과정이 매우 많기 때문에 코드를 처음부터 끝까지 다 짠다음 디버깅을 하기보다 매 과정마다 디버깅을 끝내고 넘어가는 것이 좋다. 테스트케이스가 매우 친절하다.
오늘의 교훈) 음수의 몫과 양수의 몫을 주의하자