[BOJ/백준] 23291 어항정리

import sys
def input():
    return sys.stdin.readline().rstrip()

def check(arr):
    if max(arr) - min(arr) <=K:
        return False
    return True
def push():
    min_value = min(arr[-1])
    for i in range(N):
        if arr[-1][i] == min_value:
            arr[-1][i] += 1
def roll(arr):
    row,col = 1,1
    new_N = N
    time = 0
    while True:
        new_temp = [[-1 for _ in range(new_N-col)] for _ in range(row+1)]

        for y in range(col,new_N):
            new_temp[-1][y-col] = arr[-1][y]

        for y in range(col):
            for x in range(len(arr)):
                new_temp[y][len(arr)-x-1] = arr[x][y]
        new_N = new_N-col
        if time%2:
            row += 1
            col += 1
        time += 1
        arr = [row[:] for row in new_temp]
        row_N = len(new_temp)
        if row_N*(col+1) >N:
            break
    return arr
def outOfbound(x,y,row,col):
    if 0<=x<row and 0<=y<col:
        return False
    return True
def blow():
    row = len(new_arr)
    col = len(new_arr[0])
    temp = [[0 for _ in range(col)] for _ in range(row)]
    for x in range(row):
        for y in range(col):
            if new_arr[x][y] == -1:continue
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if outOfbound(nx,ny,row,col):continue
                if new_arr[nx][ny] == -1:continue
                if new_arr[x][y] - new_arr[nx][ny] >=5:
                    gap = (new_arr[x][y] - new_arr[nx][ny])//5
                    temp[x][y] -= gap
                    temp[nx][ny] += gap
    for x in range(row):
        for y in range(col):
            new_arr[x][y] += temp[x][y]
def flatting(maze):
    temp_arr = [[]]
    row = len(maze)
    col = len(maze[0])
    for y in range(col):
        for x in range(row-1,-1,-1):
            if maze[x][y]==-1:continue
            temp_arr[-1].append(maze[x][y])
    return temp_arr
def spread():
    spread_arr = flatting(new_arr)
    temp = [[-1 for _ in range(N//4)] for _ in range(4)]

    for x in range(4):
        if x%2:
            start_x = N//4*x
            y = 0
            while y<N//4:
                temp[x][y] = spread_arr[-1][start_x+y]
                y += 1
        else:
            y = N//4-1
            if x == 2:
                start_x = 0
            else:
                start_x = N//4*2
            while y>=0:
                temp[x][y] = spread_arr[-1][start_x]
                start_x += 1
                y -= 1
    return temp
                
    
N,K = map(int,input().split())

arr = [list(map(int,input().split()))]
dx = [-1,0,1,0]
dy = [0,-1,0,1]
turn = 0
while check(arr[-1]):
    push()
    new_arr = roll(arr)
    blow()
    new_arr = spread()
    blow()
    arr = flatting(new_arr)
    turn += 1
print(turn)

 

 

삼성 기출 문제들 중에서 푸는데 제일 오래걸렸던 문제였다.

 

패턴은 찾았는데, 그걸 코드로 옮기는데 힘들었다.

 

두가지 부분이 힘들었는데 돌돌 마는 부분이랑

 

그리고 마지막에 4부분을 나눠서 합치는 부분이다.

 

이 부분엗 대한 패턴을 찾고, 그걸 코드로 옮겨주면 되는 문제였다.

 

내가 찾은 패턴은

 

돌돌 마는 패턴에서는

 

처음에

 

row 1 col1

row2 col1

row2 col2

row3 col2

row3 col3

 

접혀진 부분의 크기가 이와 같음을 알 수 있다.

 

또한 이때 다음번의 영향은 그 전의 col만큼 이후것들은 제일 밑단에 감을 알 수 있고

 

원래 말려있던 부분들은 오른쪽으로 90도 회전을 함을 알 수 있다.

 

이런 방식으로 해서 구해주면 된다.

 

 

마지막으로 4부분으로 나눠서 합치는 부분은 예제 그림을 잘 보면 패턴을 찾을 수 있다.

 

위치가 어떻게 되어있던지

 

 

1 2 3 4 5 6 7 8 9 .... 4N

 

4N 이라는 길이의 array가 있으면

 

3N 3N-1 3N-2 .... 2N+1

N+1 N+2 .... 2N

N N-1 N-2 ....    1

3N+1 3N+2 .... 4N

 

처럼 접히는것을 알 수 있고, 이걸 구현해주면 된다.

 

이 외에는 이번 삼성기출에서 풀었던 것처럼 해주면 된다.

 

이 풀이 자체는 좀 난잡하게 푼 문제라서, python으로 푸시는 분들은

 

jh05013님의 풀이를 참조하시는걸 추천드립니다.