[백준] 23291번: 어항 정리

🔈 문제

마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바닥 위에 놓여져 있다. 어항에는 물고기가 한 마리 이상 들어있다. <그림 1>은 어항 8개가 바닥 위에 놓여있는 상태이며, 칸에 적힌 값은 그 어항에 들어있는 물고기의 수이다. 편의상 어항은 정사각형으로 표현했다.

<그림 1>

어항을 한 번 정리하는 과정은 다음과 같이 이루어져 있다.

먼저, 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다. 만약, 그러한 어항이 여러개라면 물고기의 수가 최소인 어항 모두에 한 마리씩 넣는다. 위의 예시의 경우 물고기의 수가 가장 적은 어항에는 물고기가 2마리 있고, 그러한 어항은 2개가 있다. 따라서, 2개의 어항에 물고기를 한 마리씩 넣어 <그림 2>와 같아진다.

 

<그림 2>

이제 어항을 쌓는다. 먼저, 가장 왼쪽에 있는 어항을 그 어항의 오른쪽에 있는 어항의 위에 올려 놓아 <그림 3>이 된다.

 

<그림 3>

 

이제, 2개 이상 쌓여있는 어항을 모두 공중 부양시킨 다음, 전체를 시계방향으로 90도 회전시킨다. 이후 공중 부양시킨 어항을 바닥에 있는 어항의 위에 올려놓는다. 바닥의 가장 왼쪽에 있는 어항 위에 공중 부양시킨 어항 중 가장 왼쪽에 있는 어항이 있어야 한다. 이 작업은 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 있을때까지 반복한다.

먼저, <그림 4>와 같이 어항이 놓인 상태가 변하고, 한 번 더 변해서 <그림 5>가 된다.

 

<그림 4>

 

<그림 5>

 

<그림 5>에서 한 번 더 어항을 공중 부양시키는 것은 불가능하다. 그 이유는 <그림 6>과 같이 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 없기 때문이다.

<그림 6>

 

공중 부양 작업이 모두 끝나면, 어항에 있는 물고기의 수를 조절한다.

모든 인접한 두 어항에 대해서, 물고기 수의 차이를 구한다. 이 차이를 5로 나눈 몫을 d라고 하자. d가 0보다 크면, 두 어항 중 물고기의 수가 많은 곳에 있는 물고기 d 마리를 적은 곳에 있는 곳으로 보낸다. 이 과정은 모든 인접한 칸에 대해서 동시에 발생한다. 이 과정이 완료되면 <그림 7>이 된다.

 

<그림 7>

 

이제 다시 어항을 바닥에 일렬로 놓아야 한다. 가장 왼쪽에 있는 어항부터, 그리고 아래에 있는 어항부터 가장 위에 있는 어항까지 순서대로 바닥에 놓아야 한다. <그림 8>이 바닥에 다시 일렬로 놓은 상태이다.

<그림 8>

 

다시 공중 부양 작업을 해야 한다. 이번에는 가운데를 중심으로 왼쪽 N/2개를 공중 부양시켜 전체를 시계 방향으로 180도 회전 시킨 다음, 오른쪽 N/2개의 위에 놓아야 한다. 이 작업은 두 번 반복해야한다. 두 번 반복하면 바닥에 있는 어항의 수는 N/4개가 된다. <그림 9>는 이 작업을 1번 했을 때, <그림 10>은 다시 한 번 더 했을 때이다.

<그림 9>

<그림 10>

 

여기서 다시 위에서 한 물고기 조절 작업을 수행하고, 바닥에 일렬로 놓는 작업을 수행한다. <그림 10>에서 조절 작업을 마친 결과는 <그림 11>이 되고, 여기서 다시 바닥에 일렬로 놓는 작업을 수행하면 <그림 12>가 된다.

 

 

<그림 11>

 

<그림 12>

 

 

어항의 수 N, 각 어항에 들어있는 물고기의 수가 주어진다. 물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 되려면 어항을 몇 번 정리해야하는지 구해보자.

 

 

📝입력

첫째 줄에 N, K가 주어진다. 둘째에는 어항에 들어있는 물고기의 수가 가장 왼쪽에 있는 어항부터 순서대로 주어진다.

 

📑출력

 물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 되려면 어항을 몇 번 정리해야하는지 출력한다.

 

📚 문제 풀이

사실 문제의 요구 사항대로 구현을 하면 되는 문제였다.

그런데 이 문제가 플레 5까지 올라간 이유는 추측하건데 단순히 n*m 형태의 2차원 배열이 아니라 <그림 3> 과 같은 형태의 배열을 구현해야 하기에 여러 가지 신경써야할 점들이 있었다.

 

각각의 요구 사항을 함수로 뽑고 $max(물고기수) - min(물고기수) <= k$  일때까지 반복하였다.

 

 

 

아래의 함수는 가장 작은 물고기에 1을 더하는 함수이다. (더이상의 자세한 설명은 생략한다.)

 

def plus(nums: list[int]) -> list[int]:
    min_fish = min(nums)
    for i in range(n):
        if nums[i] == min_fish:
            nums[i] += 1
    return nums

 

 

아래의 함수는 공중부양 함수이다.

이때부터 리스트는 n*m 형태가 아니다. 

 

def stack(lis):
    # 가장 왼쪽에 있는 블럭을 한칸 위로 올림
    res = [[lis[0]],lis[1:]]
 
    while True:
        # 공중부양 할때 밑바닥이 있을때까지
        if len(res) > len(res[-1]) - len(res[0]):break
        idx = len(res[0])
        tmp = []
        for i in range(len(res)):
            tmp.append(res[i][:idx])
        turned = turn(tmp) # turn 함수는 90도 회전 함수이다.
        res = turned[::] + [res[-1][idx:]]
    return res

 

아래의 함수는 물고기양 조절 함수이다.

양옆과 위아래를 비교해서 차이를 5로 나눈 몫이 1이상이라면 많은 곳에서 작은 곳으로 몫만큼 이동시킨다.

 

 

def condi(lis):
    n = len(lis)
    # 변화량을 저장
    res = [[0]*len(lis[i]) for i in range(n)]
 
    for i in range(len(res)):
        for j in range(len(res[i])):
            if j != 0 and abs(lis[i][j] - lis[i][j-1])//5 > 0: # 양옆 비교
                if lis[i][j] < lis[i][j-1]:
                    res[i][j] += abs(lis[i][j] - lis[i][j-1])//5
                    res[i][j-1] -= abs(lis[i][j] - lis[i][j-1])//5
                else:
                    res[i][j] -= abs(lis[i][j] - lis[i][j-1])//5
                    res[i][j-1] += abs(lis[i][j] - lis[i][j-1])//5
            if i != 0 and len(lis[i-1]) > j and abs(lis[i][j] - lis[i-1][j])//5 > 0: # 위아래 
                if lis[i][j] < lis[i-1][j]:
                    res[i][j] += abs(lis[i][j] - lis[i-1][j])//5
                    res[i-1][j] -= abs(lis[i][j] - lis[i-1][j])//5
                else:
                    res[i][j] -= abs(lis[i][j] - lis[i-1][j])//5
                    res[i-1][j] += abs(lis[i][j] - lis[i-1][j])//5
 
    for i in range(len(res)):
        for j in range(len(res[i])):
            res[i][j] += lis[i][j] # 변화량을 반영
    return res

 

 

아래의 함수는 2차원 배열을 1차원 배열로 변경시켜주는 함수이다.

def rematch(lis):
    res = []
    n,m = len(lis), len(lis[-1])
    for j in range(m):
        for i in range(n - 1, -1, -1):
            if len(lis[i]) > j:
                res.append(lis[i][j])
    return res
 

 

 

아래의 함수는 2배로 나누고 공중부양 시키는 함수이다.

 

def levitate(lis):
    n = len(lis)
    tmp = [lis[:n//2][::-1], lis[n//2:]]
    return [tmp[-1][:n//4][::-1], tmp[0][:n//4][::-1], tmp[0][n//4:], tmp[-1][n//4:]]

 

🍭 시행착오

노실행착오

예제만 다 맞게 구현하면 틀릴 일은 없을 것 같다.

 

 

파이썬 유저중에 2등을 했다 ^!^

 

🔗 문제링크 어항 정리

23291번: 어항 정리