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님의 풀이를 참조하시는걸 추천드립니다.
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ/백준] 12912 트리 수정 (0) | 2021.12.23 |
|---|---|
| [BOJ/백준] 2240 자두나무 (0) | 2021.12.04 |
| [BOJ/백준] 23288 주사위 굴리기 2 (0) | 2021.10.27 |
| [BOJ/백준] 23290 마법사 상어와 복제 (0) | 2021.10.26 |
| [BOJ/백준] 23289 온풍기 안녕! (0) | 2021.10.25 |